Remainders.md

#coding

We all know that 5 % 3 is 2 (I use % as the modulo operation sign). What about -5 % 3 or -5 % -3 in your favorite programming language?

Turns out, there are different answers.

Python

>>> 5 % 3
2

>>> -5 % 3
1

>>> 5 % -3
-1

>>> -5 % -3
-2

What's going on? It looks like the sign of the divisor determines the "direction" to the next multiple (sign determined by the divisor sign):

• if the divisor is positive, the remainder is the distance to the first lesser multiple of the result;
• if the divisor is negative, the remainder is the distance to the first bigger multiple of the result, and this "distance" is negative.

The good thing about this scheme is that it gives different results in every case and does not throw away any sign information.

Rust

Rust has another opinion on modulos:

$ ./modulo 
5  % 3  = 2
-5 % 3  = -2
5  % -3 = 2
-5 % -3 = -2

It looks like the divisor sign is ignored and the dividend sign is carried into the result (sign determined by the dividend sign):

This scheme is easier to implement efficiently (that's why x86_64 uses it), but it's "lossy": the sign of the dividend is ignored.

C and C++

C seems to behave like Rust in this regard, but, in fact, the modulo behavior is implementation-defined, which means "do what the target CPU does" in practice. Since most of the code run today runs on x86_64, the usual behavior is "ignore the divisor sign and carry the dividend sign into the result". The rationale seems to be being close to the metal.

Haskell

Haskell exposes two functions for modulos: mod and rem. mod behaves like the Python modulo, and rem behaves like remainders in Rust.

The common folklore knowledge is that "rem is faster!". Now it's clear why: rem is closer to what x86_64 does and mod needs to check and reshuffle signs compared to rem. On the other hand, in case there were an instruction set which directly supports the choose-divisor-sign behavior, mod could be fast as well.

Conclusion

All this behavior is neatly summarized in this wiki page: https://en.wikipedia.org/wiki/Modulo_operation.

Also, this invariant is held in both cases: n = (n / m) * m + n % m.