[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窶迭abin_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: <mailto:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>