From: jzakiya@...
Date: 2016-08-19T19:59:08+00:00
Subject: [ruby-core:76986] [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.
An additional change to the implelmentation of prime_division2 provides an
another 3x increase in speed over using the generators implemented as classes.
Using class based generators, and enumerable methods, incur a metaprogamming overhead
performance hit. Creating the generators as straight methods provides more flexibility
in their use, greatly reduces the code base, and significantly increases the speed of
the prime_division method.
Below is code for prime_division3 which uses the approach of prime_division2, but creates
the prime generator parameters as a simple method.
Timings show that the code/methodology for prime_division3 is now roughly 6x the speed of
the current prime_division in prime.rb, which leaps past the goal of Ruby 3x3 for Ruby 3
to have a 3x performance increase. These performance gains will become even greater with
any language speedups developed for Ruby 3.
Testing on both 32|64 bit Linux OS systems show P17 gives the fastest results overall.
This is a physical limitation of Ruby, not a mathematical one, as the residue array sizes
past P17 exceed a million elements. If this could be improved, using P19 (and greater)
would provide even higher performance. Even still, P19 is faster for (very) large numbers
past a certain size, as it reduces the number of prime candidates (pseudo primes) to perform
brute force testing with from P17's 18.05% of all integers to P19's 17.1%.
For the mathematical basis of this see the Primes Utils Handbook.
https://www.scribd.com/document/266461408/Primes-Utils-Handbook
```
n1 = 100_000_000_000_000_003
n2 = 200_000_000_000_000_003
n3 = 1_000_000_000_000_000_003
G23 = Prime::Generator23.new
GP17 = Prime::GeneratorP17.new
n1 n2 n3
prime_division 23.7 33.5 74.6
prime_division1 22.9 32.2 72.8
prime_division2 G23 14.2 19.7 44.6
primv_division2 GP17 8.8 12.2 27.8
prime_division3 2 12.5 17.5 39.3
prime_division3 3 7.7 10.9 24.2
prime_division3 5 6.0 8.6 18.9
prime_division3 7 4.9 6.9 15.6
prime_division3 11 4.6 6.3 14.2
prime_division3 13 4.2 5.7 12.9
prime_division3 17 3.9 5.5 12.1 fastest for this range of numbers
prime_division3 19 5.2 6.9 12.8 will become faster past some larger n
class Integer
def prime_division3(pg_selector = 17)
raise ZeroDivisionError if self == 0
residues, base_primes, mod = init_generator(pg_selector)
residues = base_primes + residues
r1 = base_primes.size # first_residue_index
rn = residues.size - 1 # last_residue_index
modk = r = 0
pv = self < 0 ? [-1] : []
value = self.abs
sqrt_value = Math.sqrt(value).to_i
while (prime = modk + residues[r]) <= sqrt_value
while value % prime == 0
pv << prime
value /= prime
sqrt_value = Math.sqrt(value).to_i
end
r += 1; (r = r1; modk += mod) if r > rn
end
pv << value if value > 1
pv.group_by {|prm| prm }.map {|prm, exp| [prm, exp.size] }
end
private
def init_generator(pg_selector)
base_primes = [2, 3, 5, 7, 11, 13, 17, 19]
pg_selector = 17 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
end
```
----------------------------------------
Feature #12676: Significant performance increase, and code conciseness, for prime_division method in prime.rb
https://bugs.ruby-lang.org/issues/12676#change-60210
* 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: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>