Modulo of negative numbers

Question

Possible Duplicate:
Mod of negative number is melting my brain!

I was wondering if there was a nicer algorithm for what I'm trying to do:

wrapIndex(-6, 3) = 0
wrapIndex(-5, 3) = 1
wrapIndex(-4, 3) = 2
wrapIndex(-3, 3) = 0
wrapIndex(-2, 3) = 1
wrapIndex(-1, 3) = 2
wrapIndex(0, 3) = 0
wrapIndex(1, 3) = 1
wrapIndex(2, 3) = 2
wrapIndex(3, 3) = 0
wrapIndex(4, 3) = 1
wrapIndex(5, 3) = 2

I came up with

function wrapIndex(i, i_max) {
        if(i > -1)
            return i%i_max;

        var x = i_max + i%i_max;
        if(x == i_max)
            return 0;

        return x;
    }

Is there a nicer way to do this?

Answer 1

You could do this:

function wrapIndex(i, i_max) {
    if (i < 0) i = (i % i_max) + i_max;
    return i % i_max;
}

Answer 2

Nicer is a matter of taste, but How about

var x = (i_max + i % i_max) % i_max;

Answer 3

This solution is branchless, but performs % twice:

function wrapIndex(i, i_max) {
   return ((i % i_max) + i_max) % i_max;
}

It should be said the C#/Java behavior of % is assumed, i.e. the result has the same sign as the dividend. Some languages define the remainder calculation to take the sign of the divisor instead (e.g. mod in Clojure). Some languages have both variants (mod/rem pair in Common Lisp, Haskell, etc). Algol-68 has %x which always returns a non-negative number. C++ leaves it up to implementation.

See also

• Wikipedia/Modulo operation

Answer 4

The solution with two % operations works, but this is somewhat faster in most languages on most hardware (there are exceptions, however):

int wrapIndex(int i, int i_max) {
    i = i%i_max;
    return i<0 ? i+i_max : i;
}

Answer 5

Many users give answers, just beware negative numbers, since different languages may behave differently. By example this C snippet writes "-1"

int main ()
{
    printf("%d\n", (-4) % 3);
}

While in python we have a different output value

Python 2.6.4 (r264:75706, Dec  7 2009, 18:43:55) 
[GCC 4.4.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> (-4) % 3
2

EDIT: Actually I don't think you'll have negative indexes! However it's good to know that.

Answer 6

Why are you unsatisfied with your existing solution?