From: jzakiya@... Date: 2016-08-17T18:19:49+00:00 Subject: [ruby-core:76951] [Ruby trunk Feature#12676] Significant performance increase, and code conciseness, for prime_division method in prime.rb Issue #12676 has been updated by Jabari Zakiya. By using a faster prime generator than the current one in prime.rb the performance for the prime_division function can reach the desired 3x performance sought for Ruby 3 (3x3). ``` Timing comparisons for optimal method prime_division2 using different prime generators. Prime::Generator23 is the current generator in prime.rb. Prime::GeneratorP17 is fastest generator determined by timing all the base primes up to 23. 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 Generator23 14.2 19.7 44.6 GeneratorP17 8.8 12.2 27.8 irb(main):013:0> n = 100_000_000_000_000_003; tm{ n.prime_division2 Prime::Generator23.new} => 14.170281965 irb(main):014:0> n = 100_000_000_000_000_003; tm{ n.prime_division2 Prime::GeneratorP17.new} => 8.838717755 irb(main):015:0> n = 200_000_000_000_000_003; tm{ n.prime_division2 Prime::Generator23.new} => 19.664830177 irb(main):016:0> n = 200_000_000_000_000_003; tm{ n.prime_division2 Prime::GeneratorP17.new} => 12.209209681 irb(main):017:0> n = 1_000_000_000_000_000_003; tm{ n.prime_division2 Prime::Generator23.new} => 44.635148933 irb(main):018:0> n = 1_000_000_000_000_000_003; tm{ n.prime_division2 Prime::GeneratorP17.new} => 27.824091074 class Integer def prime_division2(generator = Prime::GeneratorP17.new) Prime.prime_division2(self, generator) end end class Prime def prime_division2(value, generator = Prime::GeneratorP17.new) raise ZeroDivisionError if value == 0 pv = value < 0 ? [-1] : [] value = value.abs sqrt_value = Math.sqrt(value).to_i generator.each do |prime| break if prime > sqrt_value while value % prime == 0 pv << prime value /= prime sqrt_value = Math.sqrt(value).to_i end end pv << value if value > 1 pv.group_by {|prm| prm }.map{|prm, exp| [prm, exp.size] } end # Generates all integers which are greater than 2 and # are not divisible by either 2 or 3. # # This is a pseudo-prime generator, suitable on # checking primality of an integer by brute force # method. class Generator23 < PseudoPrimeGenerator def initialize @prime = 1 @step = nil super end def succ if (@step) @prime += @step @step = 6 - @step else case @prime when 1; @prime = 2 when 2; @prime = 3 when 3; @prime = 5; @step = 2 end end @prime end alias next succ def rewind initialize end end # P17 Strictly-Prime Prime Generator (SP PG). # Generates all the integers greater than 17 that # are not divisible by any prime <= 17. # # This is a pseudo-prime generator, suitable for # checking primality of an integer by brute force method. class GeneratorP17 < PseudoPrimeGenerator def initialize init_generator unless @current_prime @current_prime = 1 super end # Initialize parameters for P17 Strictly-Prime Prime Generator (SP PG). # Increase/decrease base primes to pick a different SP PG. def init_generator base_primes = [2, 3, 5, 7, 11, 13, 17] @pg_mod = base_primes.reduce(:*) @residues = base_primes.dup base_primes.last.step(@pg_mod, 2) {|r| @residues << r if @pg_mod.gcd(r) == 1} @residues << @pg_mod + 1 @first_residues_index = base_primes.size @last_residues_index = @residues.size - 1 @modk = @r = 0 end # Finds/returns next pseudo-prime, and updates pointer to the next one. def succ (@modk = 0; @r = -1) if @current_prime < 2 @r += 1 (@r = @first_residues_index; @modk += @pg_mod) if @r > @last_residues_index @current_prime = @modk + @residues[@r] end alias next succ def rewind initialize end end end ``` ---------------------------------------- Feature #12676: Significant performance increase, and code conciseness, for prime_division method in prime.rb https://bugs.ruby-lang.org/issues/12676#change-60181 * Author: Jabari Zakiya * Status: Open * Priority: Normal * Assignee: ---------------------------------------- I earlier posted code to simplify the prime_division method in prime.rb. This made the code much more concise and readable/understandable, while also providing a small speed increase. The code presented here for prime_division2 maintains the conciseness and readability, but uses a different/simpler algorithm to provide a significant speed increase over the current implementation of prime_division in prime.rb. Timings for selected large primes are provided, run on CRuby 2.3.1. System: System76 3.5GHz I7 cpu laptop, Linux 64-bit OS in Virtual Box. ``` 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_division 23.7 33.5 74.6 prime_division1 22.9 32.2 72.8 prime_division2 14.8 20.5 45.8 def tm; s = Time.now; yield; Time.now - s end irb(main):015:0> n = 100_000_000_000_000_003; tm{ n.prime_division } => 23.730239721 irb(main):016:0> n = 100_000_000_000_000_003; tm{ n.prime_division1 } => 22.877657172 irb(main):017:0> n = 100_000_000_000_000_003; tm{ n.prime_division2 } => 14.758561827 irb(main):018:0> n = 200_000_000_000_000_003; tm{ n.prime_division } => 33.502851342 irb(main):019:0> n = 200_000_000_000_000_003; tm{ n.prime_division1 } => 32.23911595 irb(main):020:0> n = 200_000_000_000_000_003; tm{ n.prime_division2 } => 20.476660683 irb(main):021:0> n = 1_000_000_000_000_000_003; tm{ n.prime_division } => 74.630244055 irb(main):022:0> n = 1_000_000_000_000_000_003; tm{ n.prime_division1 } => 72.778948947 irb(main):023:0> n = 1_000_000_000_000_000_003; tm{ n.prime_division2 } => 45.802756121 1) Current code for prime_division in prime.rb. def prime_division(value, generator = Prime::Generator23.new) raise ZeroDivisionError if value == 0 if value < 0 value = -value pv = [[-1, 1]] else pv = [] end generator.each do |prime| count = 0 while (value1, mod = value.divmod(prime) mod) == 0 value = value1 count += 1 end if count != 0 pv.push [prime, count] end break if value1 <= prime end if value > 1 pv.push [value, 1] end pv end 2) Code simplification for current algorithm, increases conciseness/readability, with slight speedup. def prime_division1(value, generator = Prime::Generator23.new) raise ZeroDivisionError if value == 0 pv = value < 0 ? [[-1, 1]] : [] value = value.abs generator.each do |prime| count = 0 while (value1, mod = value.divmod(prime); mod) == 0 value = value1 count += 1 end pv.push [prime, count] unless count == 0 break if prime > value1 end pv.push [value, 1] if value > 1 pv end 3) Change of algorithm, maintains conciseness/readability with significant speed increase. def prime_division2(value, generator = Prime::Generator23.new) raise ZeroDivisionError if value == 0 pv = value < 0 ? [-1] : [] value = value.abs sqrt_value = Math.sqrt(value).to_i generator.each do |prime| break if prime > sqrt_value while value % prime == 0 pv << prime value /= prime sqrt_value = Math.sqrt(value).to_i end end pv << value if value > 1 pv.group_by {|prm| prm }.map{|prm, exp| [prm, exp.size] } end ``` -- https://bugs.ruby-lang.org/ Unsubscribe: