Saturday, March 22, 2008

Go round.. but which way?

It all started with Kushal's query about python's strange behavior regarding % operator. But my own digging went on so much that I got tempted to write an entire post than just a reply. Kushal, you might find the answer for your query somewhere at the end.

Integer division is far more interesting than one could imagine. Especially when it comes to negative numbers. Even more interesting are the topics of remainder, modulo and truncation. In general, for given two integers N and D, you would simply divide the absolute values |N| by |D| and if only one of them carries negative sign you would mark the quotient negative otherwise positive, the remainder would carry the sign of N. Now take an example,
-2/3. Your quotient would be 0 and remainder would be -2. Now try the same thing on Python. You will get
-2/3 = -1 and -2%3 = 1.
Now lets rethink of both manual and python's results.
Your manual quotient is zero because the absolute value of N is less than that of D. But thinking in terms of absolute values is just a convenient method and not the fundamental operation of division. So what is it? Can we take 3 zero times so that we will be left with -2? Is it at all correct to get a negative remainder while the portion you have chosen to divide with is positive?

And what does python does to get this apparently incorrect result? In literal sense it takes away 3 one time from -2 and you are left with 1. It could actually take 3 any number of times and the remainder would change respectively. But in most of those cases, the remainder would be greater in its absolute value than 3, so lets discard them all. But the remainder -2 and +1 are both indivisible and lesser in absolute value than three. So what decides which way is the correct one?
Things might get even complicated in practical sense with negative divisors.

Now consider the rational division which is approximately -0.6666. Thus computationally you can round it to -1. But consider -1/3. Here the rational division is -0.3333. But still, python gives the result as -1. So which way is python rounding the numbers when it comes to division? Lets take 2/3, python gives 2/3=0, which is the correct quotient. But the exact division is 0.6666 which could be rounded up to 1 rather than 0. Actually there are various ways you can truncate a given number to an integer,
1. towards the nearest integer,
2. towards zero
3. away from zero
4. round up i.e. always to the greater integer
5. and finally round down i.e. always towards lesser integer.

Manually we chose the option #2. But Python in case of division is observed to be always rounding DOWN. That is why a positive 0.6666 is rounded down to 0 and negative -0.6666 is rounded further down to -1 and not 0. This works for positive integers, but does it for negatives as well? Shouldn't it be towards zero when it comes to integer division? This is probably the reason why python behaves differently for negative number's division and modulo(%). A general formula to calculate remainder is:

rem(N,D) = N - (N/D)*D

So, assuming rounding down as python does(i.e. -2/3 = -1), the remainder for -2/3 this way comes out to be 1.
If you consider rounding up, or the manual calculation (i.e. -2/3 = 0), the remainder comes out to be -2.

So which one is correct? Lets examine few tests from maths itself.
One rule says,
(-N)/D = N/(-D) = - (N/D)

This is where python fails. Because -2/3= -1 while -(2/3) = 0.
But there is one case where python would give you the correct practical answer with the same computations. Lets first see how do we use mod functions in real life. Assume the current time in a 12 hour clock to be 9:00. You want to see what will it show after 4 hours?
So you do 9+4 which is 13 and then take the modulo 12 of this i.e. (9+4)%12=1 i.e. the remainder when you divide 13 by 12.

The same way if you want to know what time it was 10 hours back you would do:

(9-10) % 12
= -1 % 12

Going by normal way of division and remainder, you find out -1/12=0 and the remainder is -1. But which 12hr practical clock will ever show you the time to be -1? None.

Now lets do it python way. You take the division -1/12=-1 (i.e. rounding down to -1), thus according to above mentioned formula the remainder is:

-1 - (-1/12) * 12 = -1 - (-1) *12 = -1 + 12 =11

Practically 10 hours before 9 is also always 11. So python is correct here giving (9-10)%12= 11. Hurray :-)

Now one more fundamental question, is modulo, which is generally what we call the % operator, the same number as the remainder in division or not? Answer is No. After looking around for the difference between remainder and modulo, I found this:
Scroll down on the above page to get the table that illustrates different values of rem and mod functions. Now you would know that the analysis in this post is partly based on the above reference.

So finally whats the conclusion? About maths, I still could not find an affirmative source that would deny the condition (-N)/D=N/(-D)=-(N/D) and use of absolute values. So most probably python is wrong about the division, but its still only a doubt.

When it comes to modulo operator %, Python lives up to its name, i.e. modulo and returns the correct value instead of the mere remainder. This might be an effect of the probable inaccuracy in division. But its hard to imagine if it was unintentional. Specially since its different from C which leaves the confusion up to the compiler which in most cases follows the other way of correct quotient and wrong modulo. So the developers of python must be aware about this. It would be really nice if some of them could explain their own intentions and solve this riddle.