[ruby-core:76857] [Ruby trunk Feature#12665] Faster prime? method for prime.rb std lib

Issue #12665 has been updated by Marc-Andre Lafortune.


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

----------------------------------------
Feature #12665: Faster prime? method for prime.rb std lib
https://bugs.ruby-lang.org/issues/12665#change-60083

* Author: Jabari Zakiya
* Status: Closed
* Priority: Normal
* Assignee: Marc-Andre Lafortune
----------------------------------------
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
```



-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>