[ruby-core:78199] [Ruby trunk Feature#12676] Significant performance increase, and code conciseness, for prime_division method in prime.rb
From:
jzakiya@...
Date:
2016-11-18 15:46:53 UTC
List:
ruby-core #78199
Issue #12676 has been updated by Jabari Zakiya.
I refactored the last version, prime_division9, to make it simpler, which
also makes it a litlle faster. I put the base_primes factors testing in a
new int_generator2 version, which DRYs out that process into one place.
init_generator2 now takes the input number, sucks out any base_primes factors,
then selects a 'best' prime generator based on the reduced factored value, or
uses a user selected pg value. It now also returns the reduced factored value
and an array of its base_primes factors, along with the residues array and mod
value for the selected prime generator.
This refactoring now separates the main algorithmic functions into more
logically distinct methods, allowing their modification|improvement to be done
independent from each other, which allows prime_division10 to become more concise.
Also as shown, prime_division10 produces what I consider to be the mathematically
and logically correct output for -1 of `[]`, to match that for 1, instead of `[[-1,1]]`.
To produce the existing output for -1 change < -1 to < 0 in the first loc.
```
require 'openssl'
class Integer
def prime?
self.to_bn.prime?
end
def prime_division10(pg_selector = 0)
pv = self < -1 ? [-1] : [] # change < -1 to < 0 for prime.rb behavior
value = self.abs
unless value.prime? or (value | 1) == 1
residues, mod, value, factors = init_generator2(value, pg_selector)
last_residues_index = residues.size - 1
modk = r = 0
until value.prime? or value == 1
while (prime = modk + residues[r])
(factors << prime; value /= prime; break) if value % prime == 0
r += 1; (r = 0; modk += mod) if r > last_residues_index
end
end
pv += factors
end
pv << value if value > 1
pv.group_by {|prm| prm }.map{|prm, exp| [prm, exp.size] }
end
private
def init_generator2(num, pg_selector)
factors = []
base_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
base_primes.each {|prm| (factors << prm; num /= prm) while num % prm == 0 }
pg_selector = select_pg(Math.sqrt(num).to_i) unless base_primes.include? pg_selector
#puts "Using P#{pg_selector}"
mod = base_primes.select! {|prm| prm <= pg_selector }.reduce(:*)
residues = []; 3.step(mod, 2) {|r| residues << r if mod.gcd(r) == 1 }
[residues << mod + 1, mod, num, factors]
end
def select_pg(num) # adaptively select fastest SP Prime Generator
return 5 if num < 21 * 10**6 + 1000
return 7 if num < 20 * 10**9 + 1000
return 11 if num < 10 * 10**12 + 1000
return 13 if num < 70 * 10**14 - 1000
return 17 if num < 43 * 10**17 - 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-61566
* Author: Jabari Zakiya
* Status: Assigned
* Priority: Normal
* Assignee: Marc-Andre Lafortune
----------------------------------------
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
```
```ruby
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.
```ruby
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.
```ruby
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.
```ruby
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:[email protected]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>