CODEWITHSUNDEEP
python
overexchange
overexchange

Reputation: 1

Why does Python's modulus operator (%) not match the Euclidean definition?

Euclidean definition says,

Given two integers a and b, with b ≠ 0, there exist unique integers q and r such that a = bq + r and 0 ≤ r < |b|, where |b| denotes the absolute value of b.

Based on below observation,

>>> -3 % -2   # Ideally it should be (-2 * 2) + 1
-1
>>> -3 % 2    # this looks fine, (-2 * 2) + 1 
1
>>> 2 % -3    # Ideally it should be (-3 * 0) + 2
-1

looks like the % operator is running with different rules.

My question:

How do I understand the behavior of modulo operator in python? Am not aware of any other language with respect to the working of % operator.

Upvotes: 3

Views: 1100

Answers (1)

Bakuriu
Bakuriu

Reputation: 102039

The behaviour of integer division and modulo operations are explained in an article of The History of Python, namely: Why Python's Integer Division Floors . I'll quote the relevant parts:

if one of the operands is negative, the result is floored, i.e., rounded away from zero (towards negative infinity):

>>> -5//2
-3
>>> 5//-2
-3

This disturbs some people, but there is a good mathematical reason. The integer division operation (//) and its sibling, the modulo operation (%), go together and satisfy a nice mathematical relationship (all variables are integers):

a/b = q with remainder r

such that

b*q + r = a and 0 <= r < b

(assuming a and b are >= 0).

If you want the relationship to extend for negative a (keeping b positive), you have two choices: if you truncate q towards zero, r will become negative, so that the invariant changes to 0 <= abs(r) otherwise, you can floor q towards negative infinity, and the invariant remains 0 <= r < b.

In mathematical number theory, mathematicians always prefer the latter choice (see e.g. Wikipedia). For Python, I made the same choice because there are some interesting applications of the modulo operation where the sign of a is uninteresting. [...] For negative b, by the way, everything just flips, and the invariant becomes:

0 >= r > b.

In other words python decided to break the euclidean definition in certain circumstances to obtain a better behaviour in the interesting cases. In particular negative a was considered interesting while negative b was not considered as such. This is a completely arbitrary choice, which is not shared between languages.

Note that many common programming languages (C,C++,Java,...) do not satisfy the euclidean invariant, often in more cases than python (e.g. even when b is positive). some of them don't even provide any guarantee about the sign of the remainder, leaving that detail as implementation defined.

As a side note: Haskell provides both kind of moduluses and divisions. The standard euclidean modulus and division are called rem and quot, while the floored division and "python style" modulus are called mod and div.

Upvotes: 5

Related Questions