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: <mailto:ruby-core-request / ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>