[ruby-core:77045] [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.


One last simple tweek to increase overall peformance, in prime_division5.
Instead of selecting the optimum pg based on the number's size, first
suck out any factors of some base primes, then determine the optimum
pg based on the sqrt of the reduced factored number. 

This significantly speedups large factorable numbers (while maintaining
the same performance for large primes) by choosing the optimun pg for
smaller numbers resulting from the factoring by the base primes.

```
class Integer
  def prime_division5(pg_selector = 0)
    raise ZeroDivisionError if self == 0
    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

    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 = 0; 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_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-60270

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