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?

Duplicate of [Mod of negative number is melting my brain! ](http://stackoverflow.com/questions/1082917/mod-of-negative-number-is-melting-my-brain) and of at least a dozen questions on this website. :-) — ShreevatsaR, Aug 05 '10 at 17:41
Well, I searched for modulo of negative numbers and didn't really find anything... Sorry for another duplicate. — fresskoma, Aug 05 '10 at 19:58
`int mod(int k, int n) { return ((k %= n) < 0) ? k+n : k; }` — Evgeni Sergeev, Apr 22 '14 at 08:42
And in Python `(k % n)` is always positive if `n` is positive. — Evgeni Sergeev, Apr 22 '14 at 08:44

score 28 · Accepted Answer · edited May 23 '17 at 12:10

28

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++ left it up to implementation until C++11, now the sign of the remainder is (almost) fully specified according to the dividend sign.

1

+1 because it actually works. ;-) – Paul Sasik Aug 05 '10 at 17:15
1

Version with a branch returns i_max for negative multiple of i_max – Maciej Hehl Aug 05 '10 at 17:39
@Maciej: You're right; taking it out completely (since I'm not a fan of it anyway; was just trying to be "complete"). – polygenelubricants Aug 05 '10 at 17:45

score 10 · Answer 2 · answered Aug 05 '10 at 17:17

10

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;
}

answered Aug 05 '10 at 17:17

Stephen Canon

103,815
19
183
269

1

Wait, branch is faster than 2x %? Hard to believe. – Youda008 Apr 08 '18 at 08:52

score 5 · Answer 3 · answered Aug 05 '10 at 17:05

5

Nicer is a matter of taste, but How about

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

answered Aug 05 '10 at 17:05

Maciej Hehl

7,895
1
22
23

I really feel uncomfortable upvoting this, since I don't know the exact operation precedence rules for Java, or whatever language this question is asked for, but I'm sure you know what you're doing (thanks for the correction, I see that at least 3 people including me has made that error here already) – polygenelubricants Aug 05 '10 at 17:55
1

@polygenelubricants: `%` has precedence over `+` in essentially all modern languages. – Stephen Canon Aug 05 '10 at 18:28

Gumbo · Answer 4 · 2010-08-05T17:13:38.083

2

You could do this:

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

edited Aug 05 '10 at 17:13

answered Aug 05 '10 at 17:03

Gumbo

643,351
109
780
844

1

Previous version was correct :) (i % i_max) + i_max may be equal i_max if (i % i_max) == 0 – Maciej Hehl Aug 05 '10 at 17:10
1

@Maciej Hehl: Dammit, you’re right. – Gumbo Aug 05 '10 at 17:13

Dacav · Answer 5 · 2014-04-29T16:00:02.803

Many users gave good 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.

Modulo of negative numbers

5 Answers5

See also

Linked

Related