A neat trick to compute modulo of negative numbersDecember 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
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
% 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.