From: "hsbt (Hiroshi SHIBATA)" Date: 2021-11-26T05:55:05+00:00 Subject: [ruby-core:106283] [Ruby master Feature#12119] next_prime for lib/prime.rb Issue #12119 has been updated by hsbt (Hiroshi SHIBATA). Assignee deleted (yugui (Yuki Sonoda)) Status changed from Assigned to Closed prime.rb was extracted to https://github.com/ruby/prime as the bundled gems now. ---------------------------------------- Feature #12119: next_prime for lib/prime.rb https://bugs.ruby-lang.org/issues/12119#change-94908 * Author: dankogai (Dan Kogai) * Status: Closed * Priority: Normal ---------------------------------------- cf. https://github.com/ruby/ruby/pull/1272 ## Rationale To me, integer-without-limit is one of the greatest features of Ruby. I am currently working on my own implementation of arbitrary precision number system (https://github.com/dankogai/swift-pons) and ruby has been my sensei. That is why I am disappointed to find prime.rb is pretty darn impractical, even for such "small" numbers below the 64-bit boundary. Consider this: ruby -rprime -e 'p (2**61-1).prime?' # hello, anybody home? M61 is well below an ordinary, fixed, 64-bit integer can hold. This patch makes prime.rb a little more practical by: * making .prime? base upon Miller-Rabin primarity test * but unlike other patch proposals (like https://bugs.ruby-lang.org/issues/11578 ), this one is deterministic up to 318665857834031151167461, well over uint64_t max. * adding .next_prime and .prev_prime which returns the (next|previous) prime. * adding Prime::NextPrimeGenerator which makes use of .next_prime. ## vs. OpenSSL::BN Like current prime.rb, this patch is by no means to replace OpenSSL::BN.prime?. For very large numbers OpenSSL::BN is still faster. But for numbers below 32-bit limit this patch is faster. And for numbers between 32-bit limit and 64-bit limit, its performance is okay. # coding: utf-8 require 'benchmark' require 'prime' require 'openssl' count = 10000 [ 2147483647, # int32 max == M31 2147483647*2147483629, # M31 * M31.prev_prime 18446744073709551427, # the largest prime uint64_t can handle 318665857834031151167461, # A014233_11 # found at: # https://rosettacode.org/wiki/Miller���Rabin_primality_test 4547337172376300111955330758342147474062293202868155909489, # prime 4547337172376300111955330758342147474062293202868155909393 # composite ].each do |n| primerbsays = n.prime? opensslbnsays = OpenSSL::BN.new(n.to_s).prime? puts "#{n}.prime? => #{primerbsays}" puts "OpenSSL::BN.new(#{n}.to_s).prime? => #{opensslbnsays}" puts "Do they agree? #{primerbsays == opensslbnsays}" Benchmark.bm do |x| x.report("OPENSSL::BN") { count.times { OpenSSL::BN.new(n.to_s).prime? } } x.report("prime.rb") { count.times { n.prime? } } end end On my iMac (Retina 5K, 27-inch, Late 2014): 2147483647.prime? => true OpenSSL::BN.new(2147483647.to_s).prime? => true Do they agree? true user system total real OPENSSL::BN 1.320000 0.020000 1.340000 ( 1.344709) prime.rb 0.180000 0.000000 0.180000 ( 0.185658) 1152921504606846976.prime? => false OpenSSL::BN.new(1152921504606846976.to_s).prime? => false Do they agree? true user system total real OPENSSL::BN 0.010000 0.000000 0.010000 ( 0.009601) prime.rb 0.000000 0.000000 0.000000 ( 0.001034) 4611685975477714963.prime? => false OpenSSL::BN.new(4611685975477714963.to_s).prime? => false Do they agree? true user system total real OPENSSL::BN 0.150000 0.000000 0.150000 ( 0.155979) prime.rb 0.330000 0.010000 0.340000 ( 0.332222) 18446744073709551427.prime? => true OpenSSL::BN.new(18446744073709551427.to_s).prime? => true Do they agree? true user system total real OPENSSL::BN 2.080000 0.020000 2.100000 ( 2.110125) prime.rb 4.350000 0.020000 4.370000 ( 4.392225) 318665857834031151167461.prime? => false OpenSSL::BN.new(318665857834031151167461.to_s).prime? => false Do they agree? true user system total real OPENSSL::BN 0.120000 0.000000 0.120000 ( 0.126965) prime.rb 4.360000 0.010000 4.370000 ( 4.377248) 4547337172376300111955330758342147474062293202868155909489.prime? => true OpenSSL::BN.new(4547337172376300111955330758342147474062293202868155909489.to_s).prime? => true Do they agree? true user system total real OPENSSL::BN 1.780000 0.000000 1.780000 ( 1.791743) prime.rb 27.180000 0.180000 27.360000 ( 27.559330) 4547337172376300111955330758342147474062293202868155909393.prime? => false OpenSSL::BN.new(4547337172376300111955330758342147474062293202868155909393.to_s).prime? => false Do they agree? true user system total real OPENSSL::BN 0.190000 0.010000 0.200000 ( 0.194814) prime.rb 1.960000 0.000000 1.960000 ( 1.978851) ## Conclusion IMHO the gap between prime.rb and OpenSSL::BN is now unacceptably too large. It was acceptable when native integers were only 32-bit wide. But it is 2016 and even your phone may be using 64-bit int. .prime? should return instantly at least within 64-bit range. Dan the Amateur Rubyist -- https://bugs.ruby-lang.org/ Unsubscribe: