From: jzakiya@... Date: 2016-08-28T20:00:46+00:00 Subject: [ruby-core:77089] [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. OK, here's how to achieve what I believe is the ultimate brute force factoring technique, by using more resources from the Ruby Standard Library. If a number is prime we know we don't need to try and factor it. Using the very fast --prime?-- method from the OPENSSL library, we first check if the number is prime, and return ``[[self, 1]]`` if it is. If the number isn't prime then we do the following, as shown in prime_division6. Whenever we find a factor of the number, we reduce the number by that factor and then check if the new number is prime or '1'. If it's either of these we can stop factoring. So in prime_division6, inside the while loop, when a factor is found, we save it, reduce the number by it, take its square root, and jump out of the while loop into the until loop, which checks if the reduced number is prime or 1. If not, we use the same value of prime to start the while loop again (to check for multiple factors of that prime). When that prime has no (more) factors of the number, we form the next prime candidate (pseudo prime) and continue until finished. This is now much, much faster, and allows for factoring (and prime determination) of extremely large numbers, in reasonable times compared to the prior methods. Below are some timing comparisons of factorings of some 21 digit numbers. ``` 2.3.1 :006 > n = 500_000_000_000_000_000_009; n.prime_division6 => [[500000000000000000009, 1]] 2.3.1 :007 > n = 500_000_000_000_000_000_010; n.prime_division6 Using P7 => [[2, 1], [3, 1], [5, 1], [155977777, 1], [106852828571, 1]] 2.3.1 :008 > n = 500_000_000_000_000_000_011; n.prime_division6 Using P7 => [[7, 1], [49009, 1], [1457458251108397, 1]] 2.3.1 :009 > n = 500_000_000_000_000_000_012; n.prime_division6 Using P11 => [[2, 2], [482572373, 1], [259028504311, 1]] Lenovo laptop, I5 2.3 GHz, 32-bit Linux OS system. 2.3.1 :002 > def tm; s = Time.now; yield; Time.now-s end => :tm 2.3.1 :003 > n = 500_000_000_000_000_000_009; tm{ n.prime_division6 } => 0.000715062 2.3.1 :004 > n = 500_000_000_000_000_000_010; tm{ n.prime_division6 } Using P7 => 15.500916273 2.3.1 :005 > n = 500_000_000_000_000_000_011; tm{ n.prime_division6 } Using P7 => 0.006549972 2.3.1 :006 > n = 500_000_000_000_000_000_012; tm{ n.prime_division6 } Using P11 => 44.197956157 System76 laptop, I7 3.5 GHz, Virtual Box 64-bit Linux OS system. 2.3.1 :052 > n = 500_000_000_000_000_000_009; tm{ n.prime_division6 } => 0.00027761 2.3.1 :053 > n = 500_000_000_000_000_000_010; tm{ n.prime_division6 } Using P7 => 6.524573098 2.3.1 :054 > n = 500_000_000_000_000_000_011; tm{ n.prime_division6 } Using P7 => 0.005872674 2.3.1 :055 > n = 500_000_000_000_000_000_012; tm{ n.prime_division6 } Using P11 => 19.085550067 ``` Here's the complete code for prime_division6. ``` require 'openssl' class Integer def prime_division6(pg_selector = 0) return [] if self | 1 == 1 return [[self, 1]] if self.to_bn.prime? base_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] pv = self < 0 ? [-1] : [] value = self.abs base_primes.each {|prm| (pv << prm; value /= prm) while value % prm == 0 } sqrt_value = Math.sqrt(value).to_i num = self.abs == value ? value : sqrt_value residues, *, mod = init_generator1(num, pg_selector) rn = residues.size - 1; # last_residue_index modk = r = 0 until value.to_bn.prime? or value == 1 while (prime = modk + residues[r]) <= sqrt_value if value % prime == 0; pv << prime value /= prime sqrt_value = Math.sqrt(value).to_i break end r += 1; (r = 0; modk += mod) if r > rn end end pv << value if value > 1 pv.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 # puts "Using P#{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-60310 * Author: Jabari Zakiya * Status: Assigned * Priority: Normal * Assignee: Yuki Sonoda ---------------------------------------- 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: