Integer division by negative number [duplicate]

Solution 1:

Short answer: Language designers get to choose if their language will round towards zero, negative infinity, or positive infinity when doing integer division. Different languages have made different choices.

Long answer: The language authors of Python and Ruby both decided that rounding towards negative infinity makes more sense than rounding towards zero (like C does). The creator of python wrote a blog post about his reasoning here. I've excerpted much of it below.

I was asked (again) today to explain why integer division in Python returns the floor of the result instead of truncating towards zero like C.

For positive numbers, there's no surprise:

>>> 5//2
2

But 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. [update: fixed this para]

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. 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.

Solution 2:

Integer division is implementation specific. From Wikipedia's Modulo operation:

Many implementations use truncated division where the quotient is defined by truncation q = trunc(a/n), in other words it is the first integer in the direction of 0 from the exact rational quotient, and the remainder by r=a − n q. Informally speaking the quotient is "rounded towards zero", and the remainder therefore has the same sign as the dividend.

Knuth described floored division where the quotient is defined by the floor function q=floor(a/n) and the remainder r is

Here the quotient is always rounded downwards (even if it is already negative) and the remainder has the same sign as the divisor.