Issue #16468 has been updated by steveb3210 (Stephen Blackstone).


marcandre (Marc-Andre Lafortune) wrote:
> Interesting. We might as well always return the correct result, i.e. apply the fast algorithm for integers < 318,665,857,834,031,151,167,461 and the slow algorithm for larger ones. Would you care to modify your patch?

If you were to use the existing algorithm on 318,665,857,834,031,151,167,461 you'd need  Math.sqrt(318665857834031151167461 ) / 30.0 = 18_816_832_235 loop iterations..  Its not worth falling back given how inefficient the existing function is at that magnitude.


----------------------------------------
Feature #16468: Switch to Miller-Rabin for Prime.prime?
https://bugs.ruby-lang.org/issues/16468#change-83649

* Author: steveb3210 (Stephen Blackstone)
* Status: Open
* Priority: Normal
* Assignee: 
* Target version: 
----------------------------------------
The miller-rabin algorithm is a non-deterministic primality test, however it is known that below 2**64, you can always get a deterministic answer by only checking a=[2,3,5,7,11,13,17,19,23, 29, 31, 37]

Given that Prime.prime? would never respond in a reasonable amount of time for larger numbers, we can gain much more utility and performance by  switching..

```
                                               user     system      total        real
miller_rabin: random set                   0.150000   0.000000   0.150000 (  0.152212)
Prime.prime?: random set                   0.270000   0.000000   0.270000 (  0.281257)

                                               user     system      total        real
miller_rabin: 16 digits                    0.010000   0.000000   0.010000 (  0.000300)
Prime.prime? 16 digits                     2.200000   0.020000   2.220000 (  2.368247)

                                               user     system      total        real
miller_rabin: 2-10000                      0.030000   0.000000   0.030000 (  0.035752)
Prime.prime? 2-10000                       0.020000   0.000000   0.020000 (  0.022948)


---Files--------------------------------
patch.diff (1.75 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>