Python is consistent about modular arithmetic, like Mathematica

Photo by ThisisEngineering on Unsplash

In all my years of computer programming, I have accepted that modular arithmetic works differently with negative numbers than positive numbers.

For example, 13 mod 4 equals 1, and 9 mod 4 equals 1 as well, and 5 mod 4 equals 1 also, and obviously 1 mod 4 equals 1. But then −3 mod 4 equals −3, not 1, even though −3 is a number of the form 4k + 1?

That’s the answer you get with seemingly every general purpose programming language you can use today. It was the case with QBasic (take my word for it), it is the case with JavaScript and it is the case with Java, Scala and Kotlin (though there’s a caveat I’ll give at the end).

If you’re reading this on a Web browser on a laptop or desktop computer, you can easily verify how JavaScript deals with negative numbers and modular arithmetic. Open the Web browser’s console (such as with F12 on Google Chrome for Windows) and try a few different numbers.

> 13 % 4
< 1
> -3 % 4
< -3

On a Scastie snippet I made on Scastie, the official online Scala REPL, for this article, you can see how

(-47 to 49 by 4).map(_ % 4)

gives −3 several times followed by 1 several times. In another Scastie snippet, you can see that

(-50 to 50).filter(_ % 4 == 1)

only gives 1, 5, 9, …, 49, omitting −47, −43, −39, …, −3.

Of course filtering is inefficient when you can build the list with simple arithmetic, but I use it here just to keep the example simple. Filtering becomes very valuable when the incoming list is not as predictable.

Wolfram Mathematica had, to my knowledge until fairly recently, the only programming language in which a negative number modulo a positive number can be a positive number.

On Wolfram Alpha, you can verify that

Select[Range[-50, 50], Mod[#, 4] == 1 &]

gives −47, −43, −39, …, 49, as a professional mathematician would expect.

In these examples of numbers of the form 4k + 1, both −3 and 1 are technically correct as the answer to 4k + 1 mod 4.

To explain why that is, I will use principal ideals and cosets, two concepts that are very simple, despite what the unusual terminology might suggest.

Consider the set of all integers divisible by 4. In other words, all multiples of 4 in Z, where Z is the infinite set of integers …, −5, −4, −3, −2, −1, 0, 1, 2, 3, 4, 5, …

The set of multiples of 4 in Z is a principal ideal which we can notate ⟨4⟩ — or (4) if we’re feeling lazy. We can also notate it as ⟨−4⟩, since the set of all multiples of −4 is exactly the same as the set of all multiples of 4.

Now consider the set of all integers of the form 4k + 1. That is a coset of ⟨4⟩, which we can notate as ⟨4⟩ + 1. Both ⟨4⟩ and ⟨4⟩ + 1 are infinite sets that are subsets of Z, having the same density in Z: for any four consecutive integers in Z, precisely one of them is in ⟨4⟩ and precisely one of them is in ⟨4⟩ + 1 (the other two are in ⟨4⟩ + 2 and ⟨4⟩ + 3, respectively).

Just as ⟨4⟩ and ⟨−4⟩ are the same, ⟨4⟩ + 1 and ⟨4⟩ − 3 are exactly the same: they are both the set of all integers of the form 4k − 3, which is essentially the same as 4k + 1.

Therefore, it is quite correct for the Java runtime to determine that n % 4 is −3 when n is a negative member of ⟨4⟩ + 1 but n % 4 is 1 when n is a positive member of ⟨4⟩ + 1. It would also be correct to give −3 in the latter case, but I seriously doubt any runtime does that.

Indeed any member of ⟨4⟩ + 1 would be technically correct, but the modulo operator would be essentially useless if it was always just an identity operator.

This difference between how the modulo operator handles negative and positive integers becomes a problem in situations where you need your program to treat them the same.

Then you’re forced to write things like

int remainder = dividend % divisor;
if (remainder < 0) {
    remainder += divisor;
}

in Java.

But not so in Python, as the following examples from a local Python REPL show:

>>> -3 % 4
1
>>> 21 % 4
1
>>> list(filter(lambda n: n % 4 == 1, range(-50, 50)))
[-47, -43, -39, -35, -31, -27, -23, -19, -15, -11, -7, -3, 1, 5, 9, 
13, 17, 21, 25, 29, 33, 37, 41, 45, 49]

In Python, just like in Mathematica, the sign of any nonzero remainder always matches the sign of the divisor, not necessarily the sign of the dividend.

Therefore with Python it would be quite unnecessary to write

remainder = dividend % divisor
if remainder < 0 :
    remainder += divisor

like you would with Java, Scala or Kotlin.

However, in Kotlin, the Int class comes with the mod() function, which behaves the same as Python’s % operator though subject to the limitations of 32-bit integer primitives. There’s a Kotlin REPL snippet illustrating the difference in Kotlin between % and mod().