Reading this proposal I got curious as to which “true” or mathematically correct modulo implementation is the most efficient.
ECMA languages (Javascript, with CoffeeScript, and Actionscript – but also others like C++) have surprising modulo implementation which returns, most noticeably, an unexpected negative result. Here is a comparison of the differing values:
modulo -3 3 js % -3 3
----- -----
-5 | -3 -2 -5 | -3 3 -3 % 5 = -3
3 | 0 0 3 | 0 0
5 | 2 3 5 | -3 3
The surprising one is -3 % 5 = -3 and once doing anything related to mathematics, this can come up quite easily.
It seemed to me that the proposed implementation of the true modulo couldn’t be the most efficient, since it is performing Javascript modulo twice.
(a % b + b) % b
Another proposed definition was closer to my idea, using % only once, and it’s author claimed it covers some additional edge cases (I can’t seem to find them though). It uses bit-wise XOR and as it turned out from my benchmarking, XOR is pretty slow in Javascript (which might possibly have something to do with Number’s internal representation). I improved it by using != operator and compared it with my version. Here are the four functions I tested:
fastMod = (n, base) ->
if (_result = n % base) < 0 && base > 0 || _result > 0 && base < 0
_result + base
else _result
originalMod = (n, base) ->
(n % base + base) % base
saferMod = (n, base) ->
unless (jsmod = n % base) and (n > 0 ^ base > 0) then jsmod
else jsmod + base
fasterSaferMod = (n, base) ->
unless (jsmod = n % base) and ((n > 0) != (base > 0)) then jsmod
else jsmod + base
And here are some of the results, ran on varying ranges of operands:
mine: | 0.12 | 0.128 | 0.14
original: | 0.23 | 0.219 | 0.234
safer: | 0.24 | 0.185 | 0.203
safer faster: | 0.17 | 0.15 | 0.168
I used Firefox on a machine with Core i5, IE results were quite similar (just a bit slower).
My version turned out to be almost twice faster than the original proposed implementation and only slightly slower than pure % (well, the overhead of a function call is probably overshadowing the difference). The code expansion is much longer though and the real question is how often this is the bottleneck of a given application. But with CoffeeScript being increasingly used as computational tool, getting a fast implementation might be important.
To try out my test suite, open the Hot&Cold Editor with this link provided, copy the functions at the start of the code and invoke the test with compare() (use :help for help with the editor).