What's the mathematical reason behind Python choosing to round integer division toward negative infinity?

Question

I know Python // rounds towards negative infinity and in C++ / is truncating, rounding towards 0.

And here's what I know so far:

               |remainder|
-12 / 10  = -1,   - 2      // C++
-12 // 10 = -2,   + 8      # Python

12 / -10  = -1,     2      // C++
12 // -10 = -2,   - 8      # Python

12 / 10  = 1,      2       // Both
12 // 10 = 1,      2

-12 / -10 = 1,    - 2      // Both
          = 2,    + 8

C++:
1. m%(-n) == m%n
2. -m%n == -(m%n)
3. (m/n)*n + m%n == m

Python:
1. m%(-n) == -8 == -(-m%n)
2. (m//n)*n + m%n == m

But why Python // choose to round towards negative infinity? I didn't find any resources explain that, but only find and hear people say vaguely: "for mathematics reasons".

For example, in Why is -1/2 evaluated to 0 in C++, but -1 in Python?:

People dealing with these things in the abstract tend to feel that rounding toward negative infinity makes more sense (that means it's compatible with the modulo function as defined in mathematics, rather than % having a somewhat funny meaning).

But I don't see C++ 's / not being compatible with the modulo function. In C++, (m/n)*n + m%n == m also applies.

So what's the (mathematical) reason behind Python choosing rounding towards negative infinity?

---

See also Guido van Rossum's old blog post on the topic.

Answer 1

But why Python // choose to round towards negative infinity?

I'm not sure if the reason why this choice was originally made is documented anywhere (although, for all I know, it could be explained in great length in some PEP somewhere), but we can certainly come up with various reasons why it makes sense.

One reason is simply that rounding towards negative (or positive!) infinity means that all numbers get rounded the same way, whereas rounding towards zero makes zero special. The mathematical way of saying this is that rounding down towards −∞ is translation invariant, i.e. it satisfies the equation:

round_down(x + k) == round_down(x) + k

for all real numbers x and all integers k. Rounding towards zero does not, since, for example:

round_to_zero(0.5 - 1) != round_to_zero(0.5) - 1

Of course, other arguments exist too, such as the argument you quote based on compatibility with (how we would like) the % operator (to behave) — more on that below.

Indeed, I would say the real question here is why Python's int() function is not defined to round floating point arguments towards negative infinity, so that m // n would equal int(m / n). (I suspect "historical reasons".) Then again, it's not that big of a deal, since Python does at least have math.floor() that does satisfy m // n == math.floor(m / n).

---

But I don't see C++ 's / not being compatible with the modulo function. In C++, (m/n)*n + m%n == m also applies.

True, but retaining that identity while having / round towards zero requires defining % in an awkward way for negative numbers. In particular, we lose both of the following useful mathematical properties of Python's %:

1. 0 <= m % n < n for all m and all positive n; and
2. (m + k * n) % n == m % n for all integers m, n and k.

These properties are useful because one of the main uses of % is "wrapping around" a number m to a limited range of length n.

---

For example, let's say we're trying to calculate directions: let's say heading is our current compass heading in degrees (counted clockwise from due north, with 0 <= heading < 360) and that we want to calculate our new heading after turning angle degrees (where angle > 0 if we turn clockwise, or angle < 0 if we turn counterclockwise). Using Python's % operator, we can calculate our new heading simply as:

heading = (heading + angle) % 360

and this will simply work in all cases.

However, if we try to to use this formula in C++, with its different rounding rules and correspondingly different % operator, we'll find that the wrap-around doesn't always work as expected! For example, if we start facing northwest (heading = 315) and turn 90° clockwise (angle = 90), we'll indeed end up facing northeast (heading = 45). But if then try to turn back 90° counterclockwise (angle = -90), with C++'s % operator we won't end up back at heading = 315 as expected, but instead at heading = -45!

To get the correct wrap-around behavior using the C++ % operator, we'll instead need to write the formula as something like:

heading = (heading + angle) % 360;
if (heading < 0) heading += 360;

or as:

heading = ((heading + angle) % 360) + 360) % 360;

(The simpler formula heading = (heading + angle + 360) % 360 will only work if we can always guarantee that heading + angle >= -360.)

This is the price you pay for having a non-translation-invariant rounding rule for division, and consequently a non-translation-invariant % operator.

Answer 2

But why Python // choose to round towards negative infinity?

According to python-history.blogspot.com Guido van Rossum elected such behavior for // because

(...)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 (...). For Python, I made the same choice because there are some interesting applications of the modulo operation where the sign of a is uninteresting. Consider taking a POSIX timestamp (seconds since the start of 1970) and turning it into the time of day. Since there are 24*3600 = 86400 seconds in a day, this calculation is simply t % 86400. But if we were to express times before 1970 using negative numbers, the "truncate towards zero" rule would give a meaningless result! Using the floor rule it all works out fine. Other applications I've thought of are computations of pixel positions in computer graphics. I'm sure there are more.

So summing it up // behavior choice is due to keeping it consistent with % behavior, latter was selected due to its usefulness in working with negative (before start of 1970) timestamps and pixels.

Answer 3

Although I can't provide a formal definition of why/how the rounding modes were chosen as they were, the citation about compatibility with the % operator, which you have included, does make sense when you consider that % is not quite the same thing in C++ and Python.

In C++, it is the remainder operator, whereas, in Python, it is the modulus operator – and, when the two operands have different signs, these aren't necessarily the same thing. There are some fine explanations of the difference between these operators in the answers to: What's the difference between “mod” and “remainder”?

Now, considering this difference, the rounding (truncation) modes for integer division have to be as they are in the two languages, to ensure that the relationship you quoted, (m/n)*n + m%n == m, remains valid.

Here are two short programs that demonstrate this in action (please forgive my somewhat naïve Python code – I'm a beginner in that language):

C++:

#include <iostream>

int main()
{
    int dividend, divisor, quotient, remainder, check;
    std::cout << "Enter Dividend: ";                        // -27
    std::cin >> dividend;
    std::cout << "Enter Divisor: ";                         // 4
    std::cin >> divisor;

    quotient = dividend / divisor;
    std::cout << "Quotient = " << quotient << std::endl;    // -6
    remainder = dividend % divisor;
    std::cout << "Remainder = " << remainder << std::endl;  // -3

    check = quotient * divisor + remainder;
    std::cout << "Check = " << check << std::endl;          // -27
    return 0;
}

Python:

print("Enter Dividend: ")             # -27
dividend = int(input())
print("Enter Divisor: ")              # 4
divisor = int(input())
quotient = dividend // divisor;
print("Quotient = " + str(quotient))  # -7
modulus = dividend % divisor;
print("Modulus = " + str(modulus))    # 1
check = quotient * divisor + modulus; # -27
print("Check = " + str(check))

Note that, for the given inputs of different signs (-27 and 4), both the quotient and remainder/modulus are different between the languages but also that the restored check value is correct in both cases.

Answer 4

Both whole-number and real-number arithmetic define their division operators so that both of the following equivalences hold for all values of n and d.

(n+d)/d = (n/d)+1
(-n)/d = -(n/d)

Unfortunately, integer arithmetic cannot be defined in such a way that both hold. For many purposes, the first equivalence is more useful than the second, but in most situations where code would be dividing two values, one of the following would apply:

1. Both values are positive, in which case the second equivalence is irrelevant.

2. The dividend is a precise integer multiple of the divisor, in which case both equivalences can hold simultaneously.

Historically, the easiest way to handle division involving negative numbers was to observe whether exactly one operand was negative, drop the signs, perform the division, and then make the result negative if exactly one operand was. This would behave as required in both of the common situations, and would be cheaper than using an approach that would uphold the first equivalence in all cases, rather than only when the divisor was an exact multiple of the dividend.

Python shouldn't be viewed as using inferior semantics, but rather deciding that semantics which would generally be superior in cases that mattered would be worth making division slightly slower even in cases where the precise semantics wouldn't matter.

Answer 5

"for mathematics reasons"

Consider the problem (common enough in video games) where you have an X-coordinate that can be negative, and want to translate it into a tile coordinate (let's suppose 16x16 tiles) and an offset within the tile

Python's % gives you the offset directly, and / gives you the tile directly:

>>> -35 // 16 # If we move 35 pixels left of the origin...
-3
>>> -35 % 16 # then we are 13 pixels from the left edge of a tile in row -3.
13

(And divmod gives you both at once.)

Answer 6

Python's a // b = floor(a/b) in standard (ASCII) mathematic notation. (In Germany, Gauss' notation [x] is common for floor(x).) The floor function is very popular (often used ⇔ useful; google to see millions of examples). Firstly probably because it's simple & natural : "largest integer ≤ x". As a consequence, it enjoys many nice mathematical properties, like:

• Translation by an integer k: floor(x + k) = floor(x) + k.
• Euclidean division: x = y · q + r with 0 ≤ r < q := floor(x/y) for given x and y.

Any definition of the "round towards zero" function I can think of would be much more "artificial" and involve if-then's (possibly hidden in absolute value |.| or similar). I don't know of any math book that introduces a "round towards zero" function. That's already a sufficiently good reason to adopt this convention rather than the other one.

I won't be long on the "compatibility with modulo operation" argument detailed in other answers, but it must be mentioned since it's of course also a valid argument, and it's linked to the above "translation" formula. For example in trig functions, when you need the angle modulo 2 π, it's definitely this division that you will need.

Answer 7

Herein, I write div for the integer division operator and mod for the remainder operator.

div and mod must be defined such that, for a, b integers with nonzero b, we have

a == (a div b)*b + (a mod b)

Often you want mod results to always be between 0 (inclusive) and b (exclusive), regardless of the sign of a. For example, a could be an index into a circular buffer, and b could be its (positive) size. Then a mod b could be used as the index into the underlying memory array, even if a is negative. In fact, using a == -1 to refer to the last buffer element is quite popular.

This may be a reason why Python rounds quotients toward negative infinity. Thus, the remainder is either zero or has the sign of the divisor, regardless of the sign of the dividend. Here is a letter-based plot for fixed divisor:

   ^ y = x mod 5
 4 |   *    *    *    *    *
   |  *    *    *    *    *
   | *    *    *    *    *    *
   |*    *    *    *    *    *
 0 +----*----*----*----*----*->
       -5    0    5   10   15 x

In C/C++, things become a little more complicated because integers have limited width.

Suppose a == INT_MIN, which in two's-complement representation is some negative power of two, and b == 3. If we round quotients such that a mod b > 0, then (a div b)*b would have to be less than INT_MIN, which would constitute a signed-integer overflow. The effects would then be implementation-defined. The machine could even disrupt execution, e.g. when compiling with GCC's -ftrapv option. But the rationale for concretizing the behavior of the integer division and remainder operations was to get rid of such uncertainties.

Therefore the only choice left for C/C++ was to round quotients toward zero. Thus, the remainder, if nonzero, has the sign of the dividend.

The drawback is that the plot for fixed divisor looks less regular:

   ^ y = x mod 5
 4 |             *    *    *
   |            *    *    *
   |           *    *    *    *
   |          *    *    *    *
 0 |    *    *    *    *    *
   |   *    *
   |  *    *
   | *    *
-4 |*    *
   +----+----+----+----+----+->
       -5    0    5   10   15 x

Consequently, mod buffer-size does not handle negative index values as we would like. Programming-wise, I dislike this decision, although I can understand the rationale to fulfill a == (a div b)*b + (a mod b) even in extreme cases.

Answer 8

The mathematical reason behind Python choosing to round integer division toward negative infinity is that it is the most mathematically consistent option. In Python, when you divide two integers, the result will always be a floating point number. This number will be rounded to the nearest integer, with positive numbers rounding up and negative numbers rounding down. This consistent rounding behavior is what leads to the rounding toward negative infinity behavior.

The mathematical reason behind Python rounding integer division toward negative infinity is that it gives more consistent results than rounding toward positive infinity. For example, consider the following two expressions:

3 / 4

-3 / 4

The first expression will result in the value 0.75, while the second expression will result in the value -0.75. This is because the first expression rounds toward positive infinity, while the second expression rounds toward negative infinity.