Feature #12119: next_prime for lib/prime.rb - Ruby - Ruby Issue Tracking System

Actions

Copy link

Feature #12119

closed

next_prime for lib/prime.rb

Added by dankogai (Dan Kogai) about 9 years ago. Updated over 3 years ago.

Status:

Closed

Assignee:

Target version:

[ruby-core:74022]

Description

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