Project

General

Profile

Feature #12665

Faster prime? method for prime.rb std lib

Added by jzakiya (Jabari Zakiya) over 3 years ago. Updated over 3 years ago.

Status:
Closed
Priority:
Normal
Target version:
-
[ruby-core:76802]

Description

The current version of the method prime? in the prime.rb
std lib replaced the older version starting with 2.3.0.

It uses an implementation of the P3 Strictly Prime, Prime Generator (SP PG).
It can be simplified as shown below.

(see Primes-Utils Handbook for details )
(https://www.scribd.com/doc/266461408/Primes-Utils-Handbook )

A much faster version primep5? can replace it using the P5 SP PG.
This allows it to be used with bigger numbers with much better performance.

class Integer

  def prime?     # version now used in prime.rb since MRI 2.3.0
    return self >= 2 if self <= 3
    return false if self % 2 == 0 or self % 3 == 0
    # return false unless 6.gcd(self) == 1              # simplification
    (5..(self**0.5).floor).step(6).each do |i|
      if self % i == 0 || self % (i + 2) == 0
        return false
      end
    end
    true
  end

  def primep5?   # Uses P5 Strictly Prime PG
    return false unless self > 1 and 30.gcd(self) == 1 or [2,3,5].include? self
    (7..Math.sqrt(self).to_i).step(30) do |p|
      return false if 
        self%(p)    == 0 or self%(p+4)  == 0 or self%(p+6)  == 0 or self%(p+10) == 0 or
        self%(p+12) == 0 or self%(p+16) == 0 or self%(p+22) == 0 or self%(p+24) == 0
    end
    true
  end

end
``

Beloow are some timing comparisions for 3 progressively larger primes for 2.3.1.
System: System76 3.5GHz I7 cpu laptop, Linux 64-bit OS


n1 = 100_000_000_000_000_003
n2 = 200_000_000_000_000_003
n3 = 1_000_000_000_000_000_003

           n1         n2         n3

prime? 4.1 5.7 12.9
primep5 2.5 3.6 7.9

def tm; s = Time.now; yield; Time.now - s end

irb(main):028:0> n = 100_000_000_000_000_003; tm{ n.prime? }
=> 4.127392644
irb(main):029:0> n = 100_000_000_000_000_003; tm{ n.primep5? }
=> 2.539485672
irb(main):030:0> n = 200_000_000_000_000_003; tm{ n.prime? }
=> 5.721895509
irb(main):031:0> n = 200_000_000_000_000_003; tm{ n.primep5? }
=> 3.56925564
irb(main):032:0> n = 1_000_000_000_000_000_003; tm{ n.prime? }
=> 12.940908142
irb(main):033:0> n = 1_000_000_000_000_000_003; tm{ n.primep5? }
=> 7.920408959


  

Updated by jzakiya (Jabari Zakiya) over 3 years ago

The current version of the method prime? in the prime.rb
std lib replaced the older version starting with 2.3.0.

It uses an implementation of the P3 Strictly Prime, Prime Generator (SP PG).
It can be simplified as shown below.

(see Primes-Utils Handbook for details )
(https://www.scribd.com/doc/266461408/Primes-Utils-Handbook )

A much faster version primep5? can replace it using the P5 SP PG.
This allows it to be used with bigger numbers with much better performance.

class Integer

  def prime?     # version now used in prime.rb since MRI 2.3.0
    return self >= 2 if self <= 3
    return false if self % 2 == 0 or self % 3 == 0
    # return false unless 6.gcd(self) == 1              # simplification
    (5..(self**0.5).floor).step(6).each do |i|
      if self % i == 0 || self % (i + 2) == 0
        return false
      end
    end
    true
  end

  def primep5?   # Uses P5 Strictly Prime PG
    return false unless self > 1 and 30.gcd(self) == 1 or [2,3,5].include? self
    (7..Math.sqrt(self).to_i).step(30) do |p|
      return false if 
        self%(p)    == 0 or self%(p+4)  == 0 or self%(p+6)  == 0 or self%(p+10) == 0 or
        self%(p+12) == 0 or self%(p+16) == 0 or self%(p+22) == 0 or self%(p+24) == 0
    end
    true
  end

end

Beloow are some timing comparisions for 3 progressively larger primes for 2.3.1.
System: System76 3.5GHz I7 cpu laptop, Linux 64-bit OS

n1 =   100_000_000_000_000_003
n2 =   200_000_000_000_000_003
n3 = 1_000_000_000_000_000_003


               n1         n2         n3
prime?        4.1        5.7        12.9
primep5       2.5        3.6         7.9

def tm; s = Time.now; yield; Time.now - s end

irb(main):028:0> n = 100_000_000_000_000_003; tm{ n.prime? }
=> 4.127392644
irb(main):029:0> n = 100_000_000_000_000_003; tm{ n.primep5? }
=> 2.539485672
irb(main):030:0> n = 200_000_000_000_000_003; tm{ n.prime? }
=> 5.721895509
irb(main):031:0> n = 200_000_000_000_000_003; tm{ n.primep5? }
=> 3.56925564
irb(main):032:0> n = 1_000_000_000_000_000_003; tm{ n.prime? }
=> 12.940908142
irb(main):033:0> n = 1_000_000_000_000_000_003; tm{ n.primep5? }
=> 7.920408959

Updated by marcandre (Marc-Andre Lafortune) over 3 years ago

  • Assignee set to marcandre (Marc-Andre Lafortune)
  • Status changed from Open to Closed

Ok. Let's not go more complicated than this though.

Thanks

Updated by jzakiya (Jabari Zakiya) over 3 years ago

Could you please provide me a technical rationale for not giving this
method consideration. I do not know what your terse comment meant.

The method I provided is substantially faster than the current method
while having the same number of lines-of-code. What do you mean by
'more complicated' (than what).

It would be helpful for me to know what criteria you used to reject it
so I will know how to evaluate the merits of future code for consideration.

Updated by marcandre (Marc-Andre Lafortune) over 3 years ago

Sorry if I wasn't clear. It has been committed.

Also available in: Atom PDF