title: Fastest way to get a positive modulo in C/C++
body: <p>Often in my inner loops I need to index an array in a "wrap-around" way, so that (for example) if the array size is 100 and my code asks for element -2, it should be given element 98. In many high level languages such as Python, one can do this simply with <code>my_array[index % array_size]</code>, but for some reason C's integer arithmetic (usually) rounds toward zero instead of consistently rounding down, and consequently its modulo operator returns a negative result when given a negative first argument.</p>
  
  <p>Often I know that <code>index</code> will not be less than <code>-array_size</code>, and in these cases I just do <code>my_array[(index + array_size) % array_size]</code>. However, sometimes this can't be guaranteed, and for those cases I would like to know the fastest way to implement an always-positive modulo function. There are several "clever" ways to do it without branching, such as</p>
  
  <pre><code>inline int positive_modulo(int i, int n) {
      return (n + (i % n)) % n;
  }
  </code></pre>
  
  <p>or </p>
  
  <pre><code>inline int positive_modulo(int i, int n) {
      return (i % n) + (n * (i &lt; 0));
  }
  </code></pre>
  
  <p>Of course I can profile these to find out which is the fastest on my system, but I can't help worrying that I might have missed a better one, or that what's fast on my machine might be slow on a different one.</p>
  
  <p>So is there a standard way to do this, or some clever trick that I've missed that's likely to be the fastest possible way?</p>
  
  <p>Also, I know it's probably wishful thinking, but if there's a way of doing this that can be auto-vectorised, that would be amazing.</p>