0

How python calculate mathematically this modulo?

>>>-1%10  
9
Panther
  • 3,312
  • 9
  • 27
  • 50
Federico
  • 3
  • 2
  • This is more a math question: http://math.stackexchange.com/questions/519845/modulo-of-a-negative-number – karthikr Aug 17 '15 at 03:57
  • It is indeed a math question and trying a number less than negative 10 may help: divmod(-11, 10) --> -2, 9 (or -2*10 +9 = -11) –  Aug 17 '15 at 04:17
  • It looks like you were looknig for the mathematical definition of the modulo operation rather than how python calculates modulo. That's more of a math question. – skyking Aug 18 '15 at 12:34

4 Answers4

0

I'm not sure if you're asking the algorithm that python uses, or why the answer comes out this way.

If the latter, imagine that for modulo n you subtract or add n until you get a number between 0 and n-1 inclusive

Vineet Kumar Doshi
  • 4,250
  • 1
  • 12
  • 20
Dr Xorile
  • 967
  • 1
  • 7
  • 20
0

Its is caluclated like this :-
-10 / 10 = -1 ,
hence remainder 9.
-10 is greatest multiple of 10 which is less than -1.

It is similar to 9 % 5 , will be greatest number less than dividend should be considers.

5/5 = 1 , hence 4.

Vineet Kumar Doshi
  • 4,250
  • 1
  • 12
  • 20
Panther
  • 3,312
  • 9
  • 27
  • 50
0

The Wikipedia article on the modulo operation provides the following constraint for a % q:

a = nq + r

Substituting a = -1, q = 10 and r = 9, we see that n must be equal -1.

Plugging in -1 for n:

-1 % 10  # Python evaluates this as 9
-1 = n * 10 + r
-1 = -1 * 10 + r
9 = r

Testing with another example (again plugging in -1 for n):

-7 % 17  # Python evaluates this as 10
-7 = n * 17 + r
-7 = -17 + r
10 = r

A third example with a positive numerator and negative denominator:

7 % -17  # Python evaluates this as -10
7 = n * (-17) + r
7 = -1 * (-17) + r
7 = 17 + r
-10 = r

It appears that when a and q have different signs, we start with n = -1 and decrement n by 1 until we've found the n closest to zero such that n*q < a. We can test this by trying this out with an a and q such that |a| > |q|:

-100 % 11  # Python evaluates as 10
-100 = n * 11 + r
 ...   -1  # -11 > -100
 ...   -2  # -22 > -100
 ...   -3  ...
 ...   -4  ...
 ...   -5  ...
 ...   -6  ...
 ...   -7  ...
 ...   -8  ...
 ...   -9  # -99 > -100
 -100 = -10 * 11 + r  # -110 < -100
 -100 = -110 + r
 10 = r

So while this might not be the algorithm Python actually uses to calculate the modulo, we at least have a useful mental model for reasoning about how a given result was arrived at.

chucksmash
  • 5,777
  • 1
  • 32
  • 41
0

For at least python-2.7.9 it is done by first doing the integer division x/y with truncation towards zero. Then the difference of x and the quotient multiplied by y (ie x - (x/y)*y) is calculated. If the result is nonzero and y is of different sign then y is added to the result.

For example with your example x=-1 and y=10, we first calculate x/y which is 0 (-0.1 rounds to 0). The difference then is -1 - 0 which is -1. Now -1 is non-zero and with different sign than 10, so we add 10 to it and get 9.

For python3 (3.4.2) it's a bit more complicated as by python3 the integers are actually longs so the division algorithm is implemented in software rather than hardware, but otherwise basically the same. The division is done as unsigned division using the normal division algorithm using base 2^N for some suitable number N depending on platform.

skyking
  • 13,817
  • 1
  • 35
  • 57