[ruby/prime] Optimize `Integer#prime?`

Miller Rabin algorithm can be used to test primality for integers smaller than a max value "MaxMR" (~3e24)

It can be much faster than previous implementation: ~100x faster for numbers with 13 digits, at least 5 orders of magnitude for even larger numbers (previous implementation is so slow that it requires more patience than I have for more precise estimate).

Miller Rabin test becomes faster than previous implementation at somewhere in the range 1e5-1e6. It seems that the range 62000..66000 is where Miller Rabin starts being always faster, so I picked 0xffff arbitrarily; before that, or above "MaxMR", the previous implementation remains.

I compared the `faster_prime` gem too. It is slower than previous implementation up to ~1e4. After that it becomes faster and faster compared to previous implementation, but is still slower than Miller Rabin starting at ~1e5 and up to MaxMR. Thus, after this commit, builtin `Integer#prime?` will be similar or faster than `faster_prime` up to "MaxMR".

Adapted from patch of Stephen Blackstone [Feature #16468]

Benchmark results and code: https://gist.github.com/marcandre/b263bdae488e76dabdda84daf73733b9

Co-authored-by: Stephen Blackstone <sblackstone@gmail.com>

1 files changed, 11 insertions, 0 deletions

diff --git a/test/test_prime.rb b/test/test_prime.rb
index b809d15df7..8e8203e1c4 100644
--- a/test/test_prime.rb
+++ b/test/test_prime.rb
@@ -257,7 +257,18 @@ class TestPrime < Test::Unit::TestCase
       assert_not_predicate(-2, :prime?)
       assert_not_predicate(-3, :prime?)
       assert_not_predicate(-4, :prime?)
+
+      assert_equal 1229, (1..10_000).count(&:prime?)
+      assert_equal 861, (100_000..110_000).count(&:prime?)
     end
+
+=begin
+  # now Ractor should not use in test-all process
+    def test_prime_in_ractor
+      # Test usage of private constant...
+      assert_equal false, Ractor.new { ((2**13-1) * (2**17-1)).prime? }.take
+    end if defined?(Ractor)
+=end
   end
 
   def test_eratosthenes_works_fine_after_timeout