[prev in list] [next in list] [prev in thread] [next in thread] 

List:       ruby-core
Subject:    [ruby-core:74022] [Ruby trunk Feature#12119] next_prime for lib/prime.rb
From:       dankogai+ruby () gmail ! com
Date:       2016-02-27 13:53:50
Message-ID: redmine.issue-12119.20160227135350.ab84b4799c9ee9e4 () ruby-lang ! org
[Download RAW message or body]

Issue #12119 has been reported by Dan Kogai.

----------------------------------------
Feature #12119: next_prime for lib/prime.rb
https://bugs.ruby-lang.org/issues/12119

* Author: Dan Kogai
* Status: Open
* Priority: Normal
* Assignee: 
----------------------------------------
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: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>


[prev in list] [next in list] [prev in thread] [next in thread]