From: ruby-core@... Date: 2016-08-10T18:20:15+00:00 Subject: [ruby-core:76827] [Ruby trunk Feature#12665][Closed] Faster prime? method for prime.rb std lib Issue #12665 has been updated by Marc-Andre Lafortune. Status changed from Open to Closed Assignee set to Marc-Andre Lafortune Ok. Let's not go more complicated than this though. Thanks ---------------------------------------- Feature #12665: Faster prime? method for prime.rb std lib https://bugs.ruby-lang.org/issues/12665#change-60054 * 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: