From: jzakiya@... Date: 2016-08-22T18:24:21+00:00 Subject: [ruby-core:77006] [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. We can make it faster across ranges, with just a little bit more code, by adaptively selecting the Prime Generator to use based on the number size. The method select_pg has a profile of the best PG to use for given number ranges. It's added to init_generator (along with the number), and provides an adaptively selected pg, instead of a hard default previously used. In prime_division4, if no pg_selector is given then its chosen by select_pg; otherwise, if a valid pg_select value is given then it's used. ``` class Integer def prime_division4(pg_selector = 0) raise ZeroDivisionError if self == 0 residues, base_primes, mod = init_generator1(self, pg_selector) residues = base_primes + residues r1 = base_primes.size # first_residue_index rn = residues.size - 1 # last_residue_index modk = r = 0 factors = self < 0 ? [-1] : [] n = self.abs sqrt_n = Math.sqrt(n).to_i while (p = modk + residues[r]) <= sqrt_n while n % p == 0; factors << p; n /= p; sqrt_n = Math.sqrt(n).to_i end r += 1; (r = r1; modk += mod) if r > rn end factors << n if n > 1 factors.group_by {|prm| prm }.map {|prm, exp| [prm, exp.size] } end private def init_generator1(num, pg_selector) base_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23] pg_selector = select_pg(num.abs) unless base_primes.include? pg_selector base_primes.select! {|prm| prm <= pg_selector } mod = base_primes.reduce(:*) residues = []; 3.step(mod, 2) {|r| residues << r if mod.gcd(r) == 1 } [residues << mod + 1, base_primes, mod] end def select_pg(num) # adaptively select fastest SP Prime Generator return 5 if num < 1 * 10**7 + 1000 return 7 if num < 1 * 10**10 + 1000 return 11 if num < 1 * 10**13 + 1000 return 13 if num < 7 * 10**15 + 1000 return 17 if num < 4 * 10**18 + 1000 19 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-60236 * 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: