Best way to make Java's modulus behave like it should with negative numbers?
In java when you do
a % b
If a is negative, it will return a negative result, instead of wrapping around to b like it should. What's the best way to fix this? Only way I can think is
It behaves as it should a % b = a - a / b * b; i.e. it's the remainder.
You can do (a % b + b) % b
This expression works as the result of (a % b) is necessarily lower than b, no matter if a is positive or negative. Adding b takes care of the negative values of a, since (a % b) is a negative value between -b and 0, (a % b + b) is necessarily lower than b and positive. The last modulo is there in case a was positive to begin with, since if a is positive (a % b + b) would become larger than b. Therefore, b4 turns it into smaller than b again (and doesn't affect negative a values).
In number theory, the result is always positive. I would guess that this is not always the case in computer languages because not all programmers are mathematicians. My two cents, I would consider it a design defect of the language, but you can't change it now.
=MOD(-4,180) = 176
=MOD(176, 180) = 176
because 180 * (-1) + 176 = -4 the same as 180 * 0 + 176 = 176
Using the clock example here, http://mathworld.wolfram.com/Congruence.html
you would not say duration_of_time mod cycle_length is -45 minutes, you would say 15 minutes, even though both answers satisfy the base equation.
This might or might not be faster than that other formula [(a % b + b) % b]. Unlike the other formula, it contains a branch, but uses one less modulo operation. Probably a win if the computer can predict a < 0 correctly.
Java 8 has Math.floorMod, but it is very slow (its implementation has multiple divisions, multiplications, and a conditional). Its possible that the JVM has an intrinsic optimized stub for it, however, which would speed it up significantly.
The fastest way to do this without floorMod is like some other answers here, but with no conditional branches and only one slow % op.
Assuming n is positive, and x may be anything:
int remainder = (x % n); // may be negative if x is negative
//if remainder is negative, adds n, otherwise adds 0
return ((remainder >> 31) & n) + remainder;
If you only need a uniform distribution between 0 and n-1 and not the exact mod operator, and your x's do not cluster near 0, the following will be even faster, as there is more instruction level parallelism and the slow % computation will occur in parallel with the other parts as they do not depend on its result.
If the input is random in the full range of an int, the distribution of both two solutions will be the same. If the input clusters near zero, there will be too few results at n - 1 in the latter solution.