Feature #12665: Faster prime? method for prime.rb std lib

• Status: Closed
• Assignee: marcandre (Marc-Andre Lafortune)
• Target version: -

[jzakiya (Jabari Zakiya)]

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

[jzakiya (Jabari Zakiya)]

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

[marcandre (Marc-Andre Lafortune)]

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

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

Thanks

[jzakiya (Jabari Zakiya)]

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.

[marcandre (Marc-Andre Lafortune)]

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