views:

1255

answers:

12

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.

Thanks for your help.

+4  A: 

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

Tnilsson
+1  A: 

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.

Jason Baker
You surely mean: “-2 divided by 5 would be -1 with a remainder of 3”, right? This is what Python does, anyway.
ΤΖΩΤΖΙΟΥ
+1  A: 

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.

Matt Dillard
+7  A: 

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

martinatime
+3  A: 

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.

Matt Sheppard
+6  A: 

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.

Konrad Rudolph
A: 

Thanks for your help ! Now I got the thing a bit clearer. I've never thought it as substracting or adding the modulus, but thinking again about it, it is really what a division does, it is a compact way of expressing many additions or substractions.

lurks
A: 

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#).

Ozgur Ozcitak
A: 

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.

+3  A: 

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

dF
A: 

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!

Jared Updike
+2  A: 

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)
ΤΖΩΤΖΙΟΥ