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


By using a faster prime generator than the current one in prime.rb the performance for
the prime_division function can reach the desired 3x performance sought for Ruby 3 (3x3).

```
Timing comparisons for optimal method prime_division2 using different prime generators.
Prime::Generator23  is the current generator in prime.rb.
Prime::GeneratorP17 is fastest generator determined by timing all the base primes up to 23.

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
Generator23      14.2       19.7       44.6
GeneratorP17      8.8       12.2       27.8  



irb(main):013:0> n =   100_000_000_000_000_003; tm{ n.prime_division2 Prime::Generator23.new}
=> 14.170281965
irb(main):014:0> n =   100_000_000_000_000_003; tm{ n.prime_division2 Prime::GeneratorP17.new}
=> 8.838717755

irb(main):015:0> n =   200_000_000_000_000_003; tm{ n.prime_division2 Prime::Generator23.new}
=> 19.664830177
irb(main):016:0> n =   200_000_000_000_000_003; tm{ n.prime_division2 Prime::GeneratorP17.new}
=> 12.209209681

irb(main):017:0> n = 1_000_000_000_000_000_003; tm{ n.prime_division2 Prime::Generator23.new}
=> 44.635148933
irb(main):018:0> n = 1_000_000_000_000_000_003; tm{ n.prime_division2 Prime::GeneratorP17.new}
=> 27.824091074


class Integer

  def prime_division2(generator = Prime::GeneratorP17.new)
    Prime.prime_division2(self, generator)
  end

end

class Prime

  def prime_division2(value, generator = Prime::GeneratorP17.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

  # Generates all integers which are greater than 2 and
  # are not divisible by either 2 or 3.
  #
  # This is a pseudo-prime generator, suitable on
  # checking primality of an integer by brute force
  # method.
  class Generator23 < PseudoPrimeGenerator
    def initialize
      @prime = 1
      @step = nil
      super
    end

    def succ
      if (@step)
        @prime += @step
        @step = 6 - @step
      else
        case @prime
        when 1; @prime = 2
        when 2; @prime = 3
        when 3; @prime = 5; @step = 2
        end
      end
      @prime
    end

    alias next succ

    def rewind
      initialize
    end
  end

  # P17 Strictly-Prime Prime Generator (SP PG).
  # Generates all the integers greater than 17 that
  # are not divisible by any prime <= 17.
  #
  # This is a pseudo-prime generator, suitable for
  # checking primality of an integer by brute force method.
  class GeneratorP17 < PseudoPrimeGenerator
    def initialize
      init_generator unless @current_prime
      @current_prime = 1
      super
    end

    # Initialize parameters for P17 Strictly-Prime Prime Generator (SP PG).
    # Increase/decrease base primes to pick a different SP PG.
    def init_generator
      base_primes = [2, 3, 5, 7, 11, 13, 17]
      @pg_mod   = base_primes.reduce(:*)
      @residues = base_primes.dup
      base_primes.last.step(@pg_mod, 2) {|r| @residues << r if @pg_mod.gcd(r) == 1}
      @residues << @pg_mod + 1
      @first_residues_index = base_primes.size 
      @last_residues_index  = @residues.size - 1
      @modk = @r = 0
    end

    # Finds/returns next pseudo-prime, and updates pointer to the next one.
    def succ
      (@modk = 0;  @r = -1) if @current_prime < 2 
      @r += 1
      (@r = @first_residues_index; @modk += @pg_mod) if @r > @last_residues_index
      @current_prime = @modk + @residues[@r]
    end

    alias next succ

    def rewind
      initialize
    end
  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-60181

* 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>