Modulus operation with negatives values - weird thing?

Question

Can you please tell me how much is (-2) % 5? According to my Python interpreter is 3, but do you have a wise explanation for this?

I've read that in some languages the result can be machine-dependent, but I'm not sure though.

Answer 1

By the way: most programming languages would disagree with Python and give the result -2. Depending on the interpretation of modulus this is correct. However, the most agreed-upon mathematical definition states that the modulus of a and b is the (strictly positive) rest r of the division of a / b. More precisely, 0 <= r < b by definition.

Answer 2

The result of the modulus operation on negatives seems to be programming language dependent and here is a listing http://en.wikipedia.org/wiki/Modulo_operation

Answer 3

Your Python interpreter is correct. One (stupid) way of calculating a modulus is to subtract or add the modulus until the resulting value is between 0 and (modulus − 1).

e.g.: 13 mod 5 = (13 − 5) mod 5 = (13 − 10) mod 5 = 3

or in your case: −2 mod 5 = (−2 + 5) mod 5 = 3

Answer 4

Like the documentation says in Binary arithmetic operations, Python assures that:

The integer division and modulo operators are connected by the following identity: x == (x/y)*y + (x%y). Integer division and modulo are also connected with the built-in function divmod(): divmod(x, y) == (x/y, x%y).

And truly,

>>> divmod(-2, 5)
(-1, 3).

Another way to visualize the uniformity of this method is to calculate divmod for a small sequence of numbers:

>>> for number in xrange(-10, 10):
...     print divmod(number, 5)
...
(-2, 0)
(-2, 1)
(-2, 2)
(-2, 3)
(-2, 4)
(-1, 0)
(-1, 1)
(-1, 2)
(-1, 3)
(-1, 4)
(0, 0)
(0, 1)
(0, 2)
(0, 3)
(0, 4)
(1, 0)
(1, 1)
(1, 2)
(1, 3)
(1, 4)

Answer 5

Well, 0 % 5 should be 0, right?

-1 % 5 should be 4 because that's the next allowed digit going in the reverse direction (i.e., it can't be 5, since that's out of range).

And following along by that logic, -2 must be 3.

The easiest way to think of how it will work is that you keep adding or subtracting 5 until the number falls between 0 (inclusive) and 5 (exclusive).

I'm not sure about machine dependence - I've never seen an implementation that was, but I can't say it's never done.

Answer 6

As explained in other answers, there are many choices for a modulo operation with negative values. In general different languages (and different machine architectures) will give a different result.

According to the Python reference manual,

The modulo operator always yields a result with the same sign as its second operand (or zero); the absolute value of the result is strictly smaller than the absolute value of the second operand.

is the choice taken by Python. Basically modulo is defined so that this always holds:

x == (x/y)*y + (x%y)

so it makes sense that (-2)%5 = -2 - (-2/5)*5 = 3

Answer 7

Well, -2 divided by 5 would be 0 with a remainder of 3. I don't believe that should be very platform dependent, but I've seen stranger things.

Answer 8

It is indeed 3. In modular arithmetic, a modulus is simply the remainder of a division, and the remainder of -2 divided by 5 is 3.

Answer 9

The result depends on the language. Python returns the sign of the divisor, where for example c# returns the sign of the dividend (ie. -2 % 5 returns -2 in c#).

Answer 10

One explanation might be that negative numbers are stored using 2's complement. When the python interpreter tries to do the modulo operation it converts to unsigned value. As such instead of doing (-2) % 5 it actually computes 0xFFFF_FFFF_FFFF_FFFD % 5 which is 3.

Answer 11

Be careful not to rely on this mod behavior in C/C++ on all OSes and architectures. If I recall correctly, I tried to rely on C/C++ code like

float x2 = x % n;

to keep x2 in the range from 0 to n-1 but negative numbers crept in when I would compile on one OS, but things would work fine on another OS. This made for an evil time debugging since it only happened half the time!

Answer 12

There seems to be a common confusion between the terms "modulo" and "remainder".

In math, a remainder should always be defined consistent with the quotient, so that if a / b == c rem d then (c * b) + d == a. Depending on how you round your quotient, you get different remainders.

However, modulo should always give a result 0 <= r < divisor, which is only consistent with round-to-minus-infinity division if you allow negative integers. If division rounds towards zero (which is common), modulo and remainder are only equivalent for non-negative values.

Some languages (notably C and C++) don't define the required rounding/remainder behaviours and % is ambiguous. Many define rounding as towards zero, yet use the term modulo where remainder would be more correct. Python is relatively unusual in that it rounds to negative infinity, so modulo and remainder are equivalent.

Ada rounds towards zero IIRC, but has both mod and rem operators.

The C policy is intended to allow compilers to choose the most efficient implementation for the machine, but IMO is a false optimisation, at least these days. A good compiler will probably be able to use the equivalence for optimisation wherever a negative number cannot occur (and almost certainly if you use unsigned types). On the other hand, where negative numbers can occur, you almost certainly care about the details - for portability reasons you have to use very carefully designed overcomplex algorithms and/or checks to ensure that you get the results you want irrespective of the rounding and remainder behaviour.

In other words, the gain for this "optimisation" is mostly (if not always) an illusion, whereas there are very real costs in some cases - so it's a false optimisation.