Mauro Bringolf

Currently geeking out as WordPress developer at WebKinder and student of computer science at ETH.

A neat trick to compute modulo of negative numbers

December 19, 2017
, ,

Most arithmetical operations in code are different from their mathematical counterparts. They do not behave exactly the same way. Some differences can be subtle like floating point errors while others such as overflows are unavoidable. In most programming languages, the % operator on integers does not correspond to the modulo operation. It is usually explained as taking the remainder after integer division. Here are some examples in JavaScript:

12 % 5 == 2
10 % 11 == 10
3 % 2 == 1
27 % 4 == 3

on positive numbers, this is indeed the modulo operation. But not for negative numbers:

-3 % 2 == -1  // But -3 mod 2 is 1
-1 % 19 == -1 // But -1 mod 19 is 18

In JavaScript, the specification1 says that a negative number modulo a positive one yields a negative remainder. That means we cannot directly use % to create the wrap-around effect since negative numbers are mapped to negative ones. From what I have read so far it seems as if the exact behavior with negative numbers depends on the language. From here on I will refer to JavaScript’s behavior linked above: Taking % of a negative number is the same as ignoring the sign, taking the modulo of that and then adding the sign back to the result. As you can see above, this is not the same as modulo.

Constructing modulus from remainder

Assuming the behavior above, namely -x % n = – ( x mod n ) for positive n and x we can construct the desired modulo function as follows:

/**
 * Computes x mod n
 * x arbitrary integer
 * n natural number
 */
const mod = (x, n) => (x % n + n) % n

Let’s walk through the two cases:

x < 0: The innermost %-expression yields -(|x| mod n). Here |x| denotes the absolute value of x, that is the positive number you get when ignoring the sign of x. For example |-3| = 3 and |7| = 7. Therefore this result is a negative number with absolute value smaller than n. Adding n to it will yield a number between 0 and n (exclusive). Note that in arithmetic modulo n, adding or subtracting multiples of n does not change the value of the element. We just get a different representation of the same element where the usual representative is taken as the one between 0 and n. Or more precisely as a formula: x mod n = (-|x| mod n) = n – ( |x| mod n ). From this follows that the expression in parentheses correctly computes x mod n for negative numbers. So the last step taking % n does not change the value at all in this case.

x > 0: This is a lot easier. We already know that the % works like modulo if both operands are positive. That’s great because then the result of the innermost expression x % n will already be the number between 0 and n (exclusive) that we should return. And indeed, adding n and then taking modulo n will not change the value at all.

x = 0: In both cases above, the last % n step did not change the resulting value. It is necessary however, for the input x == 0. In this case x % n yields zero and adding n to it yields n. But that is not an element in arithmetic modulo n, it is equal to 0. So in this case the last % n step will change the value back to 0 which is the correct result.

References

  1. https://www.ecma-international.org/ecma-262/8.0/index.html#sec-applying-the-mod-operator