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