Python modulus the same as remainder?

Question

On the Python documentation it says "The % (modulo) operator yields the remainder from the division of the first argument by the second."

So given

a % b

From what I know, the remainder is the number left from dividing A by B evenly. So 21 % 3 = 0, and -25 % 23 = -2. What I don't understand is what happens when A is negative.

For example,

-23 % 22

Would yield

21

Which is the first positive integer that is congruent modulo -1. But -1 is the remainder of -23 % 22. So was the documentation wrong? The modulo operator % in Python does not yield the remainder in a % b, but rather that first positive integer that is in congruent modulo with B? I'm so confused.

Answer 1

There are three different obvious ways to define integer division over the negative numbers, and three corresponding ways to define remainder:

• floored division, where the quotient is floored toward negative infinity and the remainder has the same sign as the divisor.
• truncated division, where the quotient is truncated toward zero and the remainder as the same sign as the dividend.
• Euclidean division, where the quotient is truncated in whichever direction leaves the remainder positive.

All three of these preserve the fundamental law of integer division:

dividend = divisor * quotient + remainder

So, none of the three are "right" or "wrong".*

Of course that doesn't stop people from having holy wars. Knuth argued for floored division on the basis that it was "mathematically correct". Wirth argued for truncated division because it's "less surprising". Raymond Boute argued that integer division is defined in terms of the Euclidean algorithm. I won't try to settle a decades-old holy war by arguing that all three of them, including two of the most important people in the field, are wrong…

Some languages solve this problem by having two different functions.**

Let's just say that Python picked up Knuth's definition, so its modulus operator has the sign of the divisor.

---

* Of course picking non-matching definitions of quotient and remainder is another story. Or, worse, specifying one and leaving the other implementation-defined, as C did before C99.

** This is especially fun because they're not always consistent about which one is which. At least when they're called rem and mod, rem is the one that goes with div, while mod is whichever of floored or Euclidean doesn't go with div, when when they're called rem and remainder or mod and modulo…