C and Python - different behaviour of the modulo (%) operation

Question

I have found that the same mod operation produces different results depending on what language is being used.

In Python:

-1 % 10

produces 9

In C it produces -1 !

1. Which one is the right modulo?
   
2. How to make mod operation in C to be the same like in Python?

Answer 1

1. Both variants are correct, however in mathematics (number theory in particular), Python's modulo is most commonly used.
2. In C, you do ((n % M) + M) % M to get the same result as in Python. E. g. ((-1 % 10) + 10) % 10. Note, how it still works for positive integers: ((17 % 10) + 10) % 10 == 17 % 10, as well as for both variants of C implementations (positive or negative remainder).

Answer 2

Python has a "true" modulo operation, while C has a remainder operation.

It has a direct relation with how the negative integer division is handled, i.e. rounded towards 0 or minus infinite. Python rounds towards minus infinite and C(99) towards 0, but in both languages (n/m)*m + n%m == n, so the % operator must compensate in the correct direction.

Ada is more explicit and has both, as mod and rem.

Answer 3

In C89/90 the behavior of division operator and remainder operator with negative operands is implementation-defined, meaning that depending on the implementation you can get either behavior. It is just required that the operators agree with each other: from a / b = q and a % b = r follows a = b * q + r. Use static asserts in your code to check the behavior, if it relies critically on the result.

In C99 the behavior you observe has become standard.

In fact, either behaviors have certain logic in it. The Python's behavior implements the true modulo operation. The behavior you observed is C is consistent with rounding towards 0 (it's also Fortran behavior).

One of the reasons the rounding towards 0 is preferred in C is that it is rather natural to expect the result of -a / b be the same as -(a / b). In case of true modulo behavior, -1 % 10 would evaluate to 9, meaning that -1 / 10 has to be -1. This might be seen as rather unnatural, since -(1 / 10) is 0.

Answer 4

Both answers are correct since -1 modulo 10 is the same as 9 modulo 10.

r = (a mod m)
a = n*q + r

You can be sure that |r| < |n|, but not what the value of r is. There are 2 answers, negative and positive.

---

In C89, although the answer will always be correct, the exact value of a modulo operation (they refer to it as remainder) is undefined, meaning it can be either a negative result or a positive result. In C99 the result is defined.

If you want the positive answer though, you can simply add 10 if you find your answer is negative.

To get the modulo operator to work the same on all languages, just remember that:

n mod M == (n + M) mod M

and in general:

n mod M == (n + X * M) mod M

Answer 5

Performing Euclidean division a = b*q + r, is like rounding the fraction a/b to an integer quotient q, and then compute the remainder r.

The different results you see depends on the convention used for rounding the quotient...

If you round toward zero (truncate), you will get a symmetry around zero like in C:

truncate(7/3) = 2
7 = 3*2 + 1

truncate(-7/3) = -2
-7 = 3* -2 - 1

truncate(7/-3) = -2
7 = -3* -2 + 1

If you round toward negative infinity (floor), you will get a remainder like in Python:

floor(7/3) = 2
7 = 3*2 + 1

floor(-7/3) = -3
-7 = 3* -3 + 2

floor(7/-3) = -3
7 = -3* -3 - 2

If you round to nearest int (tie to whatever you want, to even, or away from zero) you'll get a centered modulo:

round(7/3) = 2
7 = 3*2 + 1

round(8/3) = 3
8 = 3*3 - 1

round(-7/3) = -2
-7 = 3* -2 - 1

round(7/-3) = -2
7 = -3* -2 + 1

You could try to implement your own modulo with rounding toward positive infinity (ceil), and you would invent a rather unconventional modulo, but it would still be kind of modulo...

Answer 6

Since python 3.7 you can also use .remainder() from math built-in module.

Python 3.7.0a0 (heads/master:f34c685020, May  8 2017, 15:35:30)
[GCC 4.2.1 Compatible Apple LLVM 8.0.0 (clang-800.0.42.1)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import math
>>> math.remainder(-1, 10)
-1.0

From docs:

Return the IEEE 754-style remainder of x with respect to y. For finite x and finite nonzero y, this is the difference x - n*y, where n is the closest integer to the exact value of the quotient x / y. If x / y is exactly halfway between two consecutive integers, the nearest even integer is used for n. The remainder r = remainder(x, y) thus always satisfies abs(r) <= 0.5 * abs(y).

Special cases follow IEEE 754: in particular, remainder(x, math.inf) is x for any finite x, and remainder(x, 0) and remainder(math.inf, x) raise ValueError for any non-NaN x. If the result of the remainder operation is zero, that zero will have the same sign as x.

On platforms using IEEE 754 binary floating-point, the result of this operation is always exactly representable: no rounding error is introduced.