Issue #14383 has been updated by jzakiya (Jabari Zakiya).


Thank you for taking this project into consideration.

FYI, there is C open source code for both the `Coreutils` [factor](https://github.com/coreutils/coreutils/blob/master/src/factor.c) function and the [APR-CL](https://sourceforge.net/projects/mpzaprcl/?source=typ_redirect) deterministic
primality test.  However, [Miller-Rabin](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) is faster, and can be implemented as deterministic, at least up 
to 25-digits, so maybe a good `Integer#prime?` method should be a hybrid combination, depending on number size.
The documentation for the APR-CL code says it's good up to 6021-digits on 64-bit systems
(not that anyone should expect to process those size numbers in any reasonable times).

To make sense of all these possibilities, a determination of the max number size|range has
to be made, since we are talking about an infinite set of numbers (primes). I wouldn't
think Ruby (or any general language) would have a primes library that will find the
largest [Mersenne Primes](https://www.mersenne.org/), for example. However, with the right math and implementation, 
thousands of digits numbers can be easily worked with within reasonable times and memory usage.

As an example, below is output of my `Integer#primesmr` method, for numerating primes
within a number range, here for 100, 1000, and 2000 digit numbers. It combines the `M-R`
test with my math techniques using `prime generators` to identify a minimum set of
`prime candidates` within the ranges, and then checking their primality.

This is part of my [primes-utils](https://github.com/jzakiya/primes-utils) gem, which has a [Primes-Utils Handbook](https://www.scribd.com/document/266461408/Primes-Utils-Handbook), 
which explains all the math, and provides the full gem source code.

It so far has the methods `primes|mr|f`, `primescnt|mr|f`, `nthprime`, `prime|mr?` and
`factors|prime_division` in current version 2.7. For the (next) 3.0 release I'm adding 
`next_prime` and `prev_prime` too.  I think these are a good (minimum) set of general 
purpose methods that provide the majority of information most people would seek in 
a primes library. I'll probably create single hybrid methods also where now I have multiple 
versions. I'm playing with JRuby for using parallel algorithms I already have implemented 
in C++/Nim until CRuby can provide capability.

Again, thanks for the Ruby team agreeing to take on this effort.

```
2.5.0 :017 > n= (10**100+267); tm{ p n.primesmr n+5000 }
[10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000267, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000949, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001243, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001293, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001983, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002773, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002809, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002911, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002967, 1000000000000000000000000000000000000000000000000000000000000000000000
 0000000000000000000000000003469, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003501, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003799, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004317, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004447, 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004491]
 => 0.06310091
2.5.0 :018 > n= (10**1000+267); tm{ p n.primesmr n+5000 }
[1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 0453, 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 0000001357, 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 0000000000002713, 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 0000000000000000004351]
 => 11.089284953
2.5.0 :019 > n= (10**2000+267); tm{ p n.primesmr n+5000 }
[1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 0004561]
 => 56.129938705
2.5.0 :020 >
```

----------------------------------------
Feature #14383: Making prime_division in prime.rb Ruby 3 ready.
https://bugs.ruby-lang.org/issues/14383#change-69989

* Author: jzakiya (Jabari Zakiya)
* Status: Open
* Priority: Normal
* Assignee: yugui (Yuki Sonoda)
* Target version: Next Major
----------------------------------------
I have been running old code in Ruby 2.5.0 (released 2017.12.25) to check for
speed and compatibility. I still see the codebase in `prime.rb` hardly has
changed at all (except for replacing `Math.sqrt` with `Integer.sqrt`).

To achieve the Ruby 3 goal to make it at least three times faster than Ruby 2
there are three general areas where Ruby improvements can occur.

* increase the speed of its implementation at the machine level
* rewrite its existing codebase in a more efficient|faster manner
* use faster algorithms to implement routines and functions

I want to suggest how to address the later two ways to improve performance of
specifically the `prime_division` method in the `prime.rb` library.


I've raised and made suggestions to some of these issues here
 [ruby-issues forum](https://bugs.ruby-lang.org/issues/12676) and now hope to invigorate additional discussion.


Hopefully with the release of 2.5.0, and Ruby 3 conceptually closer to reality,
more consideration will be given to coding and algorithmic improvements to
increase its performance too.

**Mathematical correctness**

First I'd like to raise what I consider *math bugs* in `prime_division`, in how
it handles `0` and `-1` inputs.

```
> -1.prime_division
 => [[-1,1]]

> 0.prime_division
Traceback (most recent call last):
        4: from /home/jzakiya/.rvm/rubies/ruby-2.5.0/bin/irb:11:in `<main>'
        3: from (irb):85
        2: from /home/jzakiya/.rvm/rubies/ruby-2.5.0/lib/ruby/2.5.0/prime.rb:30:in `prime_division'
        1: from /home/jzakiya/.rvm/rubies/ruby-2.5.0/lib/ruby/2.5.0/prime.rb:203:in `prime_division'
ZeroDivisionError (ZeroDivisionError)
```
First, `0` is a perfectly respectable integer, and is non-prime, so its output should be `[]`, 
an empty array to denote it has no prime factors. The existing behavior is solely a matter of 
`prime_division`'s' implementation, and does not take this mathematical reality into account.

The output for `-1` is also mathematically wrong because `1` is also non-prime (and correctly 
returns `[]`), well then mathematically so should `-1`.  Thus, `prime_division` treats `-1` as 
a new prime number, and factorization, that has no mathematical basis.  Thus, for mathematical 
correctness and consistency `-1` and `0` should both return `[]`, as none have prime factors.

```
> -1.prime_division
 => []

> 0.prime_division
 => []

> 1.prime_division
 => []
```
There's a very simple one-line fix to `prime_division` to do this:

```
# prime.rb

class Prime

  def prime_division(value, generator = Prime::Generator23.new)
    -- raise ZeroDivisionError if value == 0
    ++ return [] if (value.abs | 1) == 1
```

**Simple Code and Algorithmic Improvements**

As stated above, besides the machine implementation improvements, the other
areas of performance improvements will come from coding rewrites and better
algorithms. Below is the coding of `prime_division`. This coding has existed at
least since Ruby 2.0 (the farthest I've gone back).

```
# prime.rb

class Integer

  # Returns the factorization of +self+.
  #
  # See Prime#prime_division for more details.
  def prime_division(generator = Prime::Generator23.new)
    Prime.prime_division(self, generator)
  end

end

class Prime

  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

end
```

This can be rewritten in more modern and idiomatic Ruby, to become much shorter
and easier to understand.

```
require 'prime.rb'

class Integer
  def prime_division1(generator = Prime::Generator23.new)
    Prime.prime_division1(self, generator)
  end
end

class Prime

  def prime_division1(value, generator = Prime::Generator23.new)
    # raise ZeroDivisionError if value == 0
    return [] if (value.abs | 1) == 1
    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

end
```
By merely rewriting it we get smaller|concise code, that's easier to understand,
which is slightly faster. A *triple win!* Just paste the above code into a 2.5.0
terminal session, and run the benchmarks below.

```
def tm; s=Time.now; yield; Time.now-s end

 n = 500_000_000_000_000_000_008_244_213; tm{ pp n.prime_division }
[[3623, 1], [61283, 1], [352117631, 1], [6395490847, 1]]
 => 27.02951016

 n = 500_000_000_000_000_000_008_244_213; tm{ pp n.prime_division1 }
[[3623, 1], [61283, 1], [352117631, 1], [6395490847, 1]]
 => 25.959149721
```
Again, we get a *triple win* to this old codebase by merely rewriting it. It can
be made 3x faster by leveraging the `prime?` method from the `OpenSSL` library to
perform a more efficient|faster factoring algorithm, and implementation.

```
require 'prime.rb'
require 'openssl'

class Integer

  def prime_division2(generator = Prime::Generator23.new)
    return [] if (self.abs | 1) == 1
    pv = self < 0 ? [-1] : []
    value = self.abs
    prime = generator.next
    until value.to_bn.prime? or value == 1
      while prime
        (pv << prime; value /= prime; break) if value % prime == 0
        prime = generator.next
      end
    end
    pv << value if value > 1
    pv.group_by {|prm| prm }.map{|prm, exp| [prm, exp.size] }
  end

end
```
Here we're making much better use of Ruby idioms and libraries (`enumerable` and
`openssl`), leading to a much greater performance increase. A bigger *triple win*.
Pasting this code into a 2.5.0 terminal session gives the following results.

```
# Hardware: System76 laptop; I7 cpu @ 3.5GHz, 64-bit Linux

def tm; s=Time.now; yield; Time.now-s end

 n = 500_000_000_000_000_000_008_244_213; tm{ pp n.prime_division }
[[3623, 1], [61283, 1], [352117631, 1], [6395490847, 1]]
 => 27.02951016

 n = 500_000_000_000_000_000_008_244_213; tm{ pp n.prime_division1 }
[[3623, 1], [61283, 1], [352117631, 1], [6395490847, 1]]
 => 25.959149721

 n = 500_000_000_000_000_000_008_244_213; tm{ pp n.prime_division2 }
[[3623, 1], [61283, 1], [352117631, 1], [6395490847, 1]]
 => 9.39650374
```
`prime_division2` is much more usable for significantly larger numbers and use
cases than `prime_division`. I can even do multiple times better than this, if
you review the above cited forum thread.

My emphasis here is to show there are a lot of possible *low hanging fruit*
performance gains ripe for the picking to achieve Ruby 3 performance goals, if we
look (at minimum) for simpler|better code rewrites, and then algorithmic upgrades.

So the question is, are the devs willing to upgrade the codebase to provide the
demonstrated performance increases shown here for `prime_division`?

---Files--------------------------------
bm.rb (1.94 KB)


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