What determines the sign of m % n for integers?

Question

The modulo in Python is confusing.

In Python, % operator is calculating the remainder:

>>> 9 % 5
4

However:

>>> -9 % 5
1

Why is the result 1? and not -4?

Avaunt

This wikipedia article on Modular arithmetic should clear it up – Estevan

Answer 1

Because in python, the sign matches the denominator.

>>> 9 % -5
-1
>>> -9 % 5
1

For an explanation of why it was implemented this way, read the blog post by Guido.

Ilowell

ooops sry i meant why is the answer 1 and not -4? – Avaunt

-4+5 = 1, match the sign – Hawks

Answer 2

-10 % 5 is 0, ie, -10 is evenly divided by 5.

You ask why -9 % 5 is not -4, and the answer is that both 1 and -4 can be correct answers, it depends on what -9 divided by 5 is. Of course -9 divided by 5 is 1.8, but this is integer division, in Python 3 represented by //, so I'll use // here to be clear that it's integer division we are talking about.

I'll explain this by not using negative numbers, it's easier.

9 // 5 is 1. Ie, you can subtract 5 from 9 only 1 time, and the rest is 4. But if you subtract 5 from 9 one more time, well, then the rest becomes -1!

So -1 is a correct answer to 9 % 5, if 9 // 5 is 2.

In Python 9 // 5 is 1, because the Python integer division is a floor division, ie it always rounds down. If it has rounded up 9 // 5 would be two, and 9 % 5 would have been -1.

Now lets look at the case when we use negative numbers: -9 divided by 5 is now -2. Because it is floor division, it always rounds down. That means that the rest is 1. So -9 % 5 is 1, not -4.

Inequality

Answer 3

This really has to do with how python rounds integer division.

Mathematically, the following has to be true always for any int x and y

x == (x // y) * y + x % y

So from this, we can say

x % y == x - (x // y) * y

Now recall that python rounds integer divison toward negative infinity, not toward zero. For example -9 // 5 gives -2, not -1. With this logic, you obtain -9 % 5 = 1

Snout

Answer 4

Think about it like this:

0 % 5 is 0

1 % 5 is 1

So... what if you go backwards?

-1 % 5 must be 4

-2 % 5 must be 3

and so on.

You'll see that following this -9 % 5 is 1

NOTE: Depending on the programming language and the implementation of %, you might get different results since programmers disagree on how to handle negative numbers in %

Perdurable

maybe i have this understanding of % all wrong. if x%y, doesnt that represent the remainder after x has been divided into y? – Avaunt

It represents something slightly different, but incredibly useful. Basically, it allows you to mod numbers and consider them to be in ranges of 0 to n-1 even when they go negative. The link wim posted gives an example of why you might want this: python-history.blogspot.com.au/2010/08/… – Perdurable

could you explain why 3%7 is 3. i mean by my logic up there, 3 is the remainder after 3 has been divided into 7?? im confused :( – Avaunt

Yes, 3%7 is 3. And 0%7 is 0, and -1%7 is 6 - because 6%7 is also 6, and (m+a*n)%n always equals m%n for any positive or negative integer a. (e.g. you can subtract or add 7 and still get the same remainder) – Perdurable

Answer 5

In integers, you can't always pick such a quotient that quotient * divisor == dividend. If the product does not equal the dividend, one always has to make a choice, whether to make it slightly less than the dividend, or slightly greater than the dividend. The sum of the product with the remainder makes the dividend, that's what the remainder is. In any case, the dividends and products have to be close, meaning the absolute value of the remainder has to be less than that of the divisor.

When the divisor is positive, the products increase as the quotients increase; when the divisor is negative, the products decrease as the quotients increase. In the first case, the products go from the below, in the second case, the products go from the above. In Python, in both cases the next quotient is only taken when the dividend reaches the next possible product, going the same way the products go. Before that, only the remainder changes to accommodate for the next dividend, again always going in the same direction as the dividends change, without a break at zero. This rule is universal in Python, it holds always.

That is not the reason why this choice had been made, but that gives the idea what happens (i. e. why the results are what they are, and which results to expect).

Wapentake

Answer 6

I'll write the calculation as a math procedure with your example.

For -9 % 5:

1. Do float division of -9 (dividend) by 5(divisor). Result is -1.8
2. Take floor of result. i.e. floor of -1.8 = -2. Floor takes you to the lesser integer. Please notice the difference with flooring for negative and positive floats. So, quotient = -2.
3. With data above: dividend = quotient x divisor + remainder

=> -9 = -2 x 5 + remainder

=> -9 = -10 + remainder

=> remainder = 1

So, -9 % 5 = 1 in Python.

Whaleback