Published: Mon 22 June 2015
By greenca
In Computer .
tags: python C++
Suppose you need to know if a given number is a multiple of, say, 5. There's a simple solution to this problem: the modulo operator. In many languages, it looks like this:
And what it returns is the remainder when dividing x by 5. If that remainder is 0, then x is divisible by 5. Simple.
But... what if x is a negative number? Or what if instead of 5, you used -5? What is the "remainder" in those situations?
Here's what happens if we try it out in Python:
>> 13 % 5
3
>> -13 % 5
2
>> 13 % -5
-2
>> -13 % -5
-3
But what if we try the same thing in C++?
>> 13 % 5
3
>> -13 % 5
-3
>> 13 % -5
3
>> -13 % -5
-3
This is troubling. What's going on here?
It turns out that there are three different ways to define the modulo operation, and, depending on which you choose, you get a completely different answer in the cases where any of the arguments are negative. Furthermore, despite the fact that many programming languages use the same symbol to represent the modulo operator, they have defined the operation differently. So an identical calculation can give completely different results, depending on the language it's written in.
The three different types of modulo are based on the different ways of defining integer division. Which makes sense, since, if the modulo is the "remainder", then we need to know what the integer result of the division is, in order to know how much remainder is left over. So, on to the types of integer division.
Truncated Division
Truncated Division defines integer division as though it was float division, with everything after the decimal place removed (i.e. the result is truncated, as the name suggests).
7 / 3 = 2.333..., then the integer quotient is 2. 7 - 3 * 2 = 1.
-7 / 3 = -2.333..., then the integer quotient is -2. -7 - 3 * (-2) = -1.
7 / -3 = -2.333..., then the integer quotient is -2. 7 - (-3) * (-2) = 1.
-7 / -3 = 2.333..., then the integer quotient is 2. -7 - (-3) * 2 = -1.
Floored Division
Floored Division defines integer division as the floor of the float division, the largest integer less than or equal to the float division.
7 / 3 = 2.333..., then the integer quotient is floor(2.333...) = 2. 7 - 3 * 2 = 1.
-7 / 3 = -2.333..., then the integer quotient is floor(-2.333...) = -3. -7 - 3 * (-3) = 2.
7 / -3 = -2.333..., then the integer quotient is floor(-2.333...) = -3. 7 - (-3) * (-3) = -2.
-7 / -3 = 2.333..., then the integer quotient is floor(2.333...) = 2. -7 - (-3) * 2 = -1.
Euclidean Division
Unlike the previous two definition, Euclidean Division is defined by the remainder, rather than the quotient itself. It is based on the requirement that the remainder never be a negative number. For the division a / b (where b is not zero), there are unique integers q and r such that a = bq + r and 0 <= r < |b|. q is defined to be the quotient (the result of the integer division), and r is the remainder (the result of the modulo operation).
If a = 7 and b = 3, then q = 2 and r = 1, since 7 = 3 * 2 + 1.
If a = -7 and b = 3, then q = -3 and r = 2, since -7 = 3 * (-3) + 2.
If a = 7 and b = -3, then q = -2 and r = 1, since 7 = (-3) * (-2) + 1.
If a = -7 and b = -3, then q = 3 and r = 2, since -7 = (-3) * 3 + 2.
Comparison
Dividend Divisor Truncated Division Floored Division Euclidean Division
7 3 q = 2, r = 1 q = 2, r = 1 q = 2, r = 1
-7 3 q = -2, r = -1 q = -3, r = 2 q = -3, r = 2
7 -3 q = -2, r = 1 q = -3, r = -2 q = -2, r = 1
-7 -3 q = 2, r = -1 q = 2, r = -1 q = 3, r = 2
As the table above demonstrates, the modulo matches the sign of the Dividend under Truncated Division, and matches the sign of the Divisor under Floored Division. And the modulo is always positive under Euclidean Division.
Programming Languages
Each programming language has chosen a definition to use for it's default modulo operator. (A few languages have multiple variations defined, under different keywords/operators.)
Python has defined % using Floored Division. It also offers the Truncated Division definition as math.fmod.
C++ % used to be implementation-defined (which is a pretty bad option, since you can't count on anything), while div was Truncated Division. As of ISO 2011, they are both Truncated Division.
Some math-focused languages like Matlab and Julia do both: mod is Floored Division and rem is Truncated Division. Another, Maple, is one of the few that has gone with Euclidean Division.
Luckily, they all match when everything is positive, so you can confidently solve FizzBuzz in any language. But as soon as any negative numbers are a possibility, be very wary...