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


I am confused some by these recent comments, and would appreciate clarification.

Since 1 is not prime and returns [] then for mathematical consistency and correctness so should -1.

I don't understand how the code I presented created a problem. It presents no problems in my benchmarks.
The alternative to it then would be:

```
    return [] if self == 0 or self.abs == 1
``` 

Actually, the code fixes handling -1 correctly and also correctly mathematically handles 0 (no error raised).
If you allow these mathematical errors to remain the code produces the same results as `prime_division` and is 
thus a drop in replacement for it (but much faster). Have you tested it?

Besides these math errors, the current version of `prime_divison` is slow and uses much more code than necessary.
My purpose is to make prime factorization in `prime.rb` as fast as possible, particulary to exceed Matz's Ruby 3x3 goal. 
The code I've presented is orders of magnitude faster than 3x, with the added benefit of greatly reducing the codebase
necessary to achieve this performance increase. On my 3.5GHz I7 Linux laptop it can factor 30+ digit numbers in seconds.
Have you benchmarked it against `prime_division`? Are there other more important metrics that the code is being judged against?

As a user of Ruby for math and engineering purposes I need accuracy, speed, and ease of use.
The present handling of -1 and 0 are just plain mathematical errors. In fact, from a mathematical perspective *all negative 
integers are defined as non-prime*, so from that perspective you don't even need to try to prime factor negative numbers. 
In my `primes-utils` gem I just do `self.abs` to require processing only positve integers.

Also, by using the `OpenSSL` Standard Library you can replace the slow implementation of `prime?` with it's counterpart 
to increase performance, and save code too.

Below is the even more concise improved code. As you see, it's much shorter than the current codebase in `prime.rb`.
If Ruby ever gets true parallel programming capabilities it could possibly be upgraded to take advantage of that too.
If you have questions please let me know. 

```
require 'openssl'

class Integer 

  def prime?
    self.to_bn.prime?
  end

  def prime_division9(pg_selector = 0)
    return [] if self.abs | 1 == 1
    return [[self, 1]] if self.prime?
    pv = self < 0 ? [-1] : []
    value = self.abs
    base_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
    base_primes.each {|prm| (pv << prm; value /= prm) while value % prm == 0 }
    
    unless value.prime? or value == 1
      residues, *, mod = init_generator1(Math.sqrt(value).to_i, pg_selector)
      rn = residues.size - 1
      modk = r = 0

      until value.prime? or value == 1
        while (prime = modk + residues[r])   
          (pv << prime; value /= prime; break) if value % prime == 0
          r += 1; (r = 0; modk += mod) if r > rn
        end
      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 < 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-60797

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