FYI
Submitted a new Ruby version to perform the Miller-Rabin Primality test that’s deterministic for at least
n < 3_317_044_064_679_887_385_961_981.
It is also correctly implemented to use optimum bases > input n.
See https://miller-rabin.appspot.com/.
I also submitted equivalent versions in Crystal and Nim.
Ruby: https://rosettacode.org/wiki/Miller–Rabin_primality_test#Ruby
Crystal: https://rosettacode.org/wiki/Miller–Rabin_primality_test#Crystal
Nim: https://rosettacode.org/wiki/Miller–Rabin_primality_test#Nim
Good, Thank you.
Have you compare times execution between Ruby/Crystal/Nim ?
The Ruby version is much faster than the Crystal and Nim versions (though they do the same algorithm) because Ruby has a fast implementation of the modular exponentiation function mod_exp hidden in the openssl library. I say hidden because I only learned of its existence when seeing it used in someone else’s code. (Someone needs to do a comprehensive article on all the numerical functions contained in the library).
Currently, Nim doesn’t have any library (std or add on) for doing (fast) arbitrary size integer math, so the Nim version only works over 64-bits (would need modding for 32-bits).
Crystal has a big std library for doing arbitrary size integer math, but doesn’t have the comparable (fast) modular math functions in openssl. I suspect (?) once Crystal has these comparable functions it should be as fast as Ruby. But I have to say, I’m very impressed with Ruby’s implementations of these functions. I’ve tested numbers in the thousands of digits|bits and the response is virtually instant for those numbers too.
One thing I think can speed up the Ruby version (maybe Crystal too) is to replace the hash of witness bases with a faster structure. I know in truffleruby hashes are much slower than arrays.
In Nim, I also did 2 implementations to do the base tests in parallel. It definitely was significantly faster as the number get larger. Nim has a nice simple architecture to do parallel processing, something I can’t wait for CRuby to obtain (haven’t tried to learn with JRuby|TruffleRuby).
Finally, I’m currently playing around with creating a deterministic prime test simpler|faster than M-R, and have it partially working correctly for n < 1_000_000 (16 wrong values). It’s an interesting exercise. 