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.
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
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.
% 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 three 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
% ndoes 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 % nwill 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
% nstep 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
% nstep will change the value back to 0 which is the correct result.