* [ruby-core:96600] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime?
[not found] <redmine.issue-16468.20191230192711@ruby-lang.org>
@ 2019-12-30 19:27 ` sblackstone
2020-01-04 19:19 ` [ruby-core:96664] " sblackstone
` (4 subsequent siblings)
5 siblings, 0 replies; 6+ messages in thread
From: sblackstone @ 2019-12-30 19:27 UTC (permalink / raw)
To: ruby-core
Issue #16468 has been reported by steveb3210 (Stephen Blackstone).
----------------------------------------
Feature #16468: Switch to Miller-Rabin for Prime.prime?
https://bugs.ruby-lang.org/issues/16468
* 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)
```
```
require 'benchmark'
require 'prime'
def modpow(base, power, mod)
result = 1
while power > 0
result = (result * base) % mod if power & 1 == 1
base = (base * base) % mod
power >>= 1;
end
result
end
def miller_rabin(n)
return false if n < 2 # 0, 1
return true if n < 4 # 2, 3
return false if n % 2 == 0 # 4, 6, 8, 10
d = (n-1)
s = 0
while (d % 2 == 0)
s +=1
d /= 2
end
# https://arxiv.org/pdf/1509.00864.pdf
#
# if n < 18,446,744,073,709,551,616 = 2**64, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37.
#
[2,3,5,7,11,13,17,19,23, 29, 31, 37].each do |a|
x = modpow(a,d,n)
next if x == 1 or x == (n - 1) or n == a
skip = false
1.upto(s-1) do |k|
x = x*x % n
if x == 1
return false
elsif x == (n - 1)
skip = true
break
end
end
next if skip
return false
end
return true
end
test_set = []
while test_set.length < 50_000
test_set << rand(1_000_000)
end
c = 1
Benchmark.bm(40) do |bm|
bm.report("miller_rabin: random set") do
test_set.each do |x|
miller_rabin(x)
end
end
bm.report("Prime.prime?: random set") do
test_set.each do |x|
Prime.prime?(x)
end
end
end
puts
Benchmark.bm(40) do |bm|
bm.report("miller_rabin: 16 digits") do
miller_rabin(1000000000100011)
end
bm.report("Prime.prime? 16 digits") do
Prime.prime?(1000000000100011)
end
end
puts
Benchmark.bm(40) do |bm|
bm.report("miller_rabin: 2-10000") do
(2..10000).each do |x|
miller_rabin(x)
end
end
bm.report("Prime.prime? 2-10000") do
(2..10000).each do |x|
Prime.prime?(x)
end
end
end
```
--
https://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 6+ messages in thread
* [ruby-core:96664] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime?
[not found] <redmine.issue-16468.20191230192711@ruby-lang.org>
2019-12-30 19:27 ` [ruby-core:96600] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime? sblackstone
@ 2020-01-04 19:19 ` sblackstone
2020-01-04 23:09 ` [ruby-core:96665] " ruby-core
` (3 subsequent siblings)
5 siblings, 0 replies; 6+ messages in thread
From: sblackstone @ 2020-01-04 19:19 UTC (permalink / raw)
To: ruby-core
Issue #16468 has been updated by steveb3210 (Stephen Blackstone).
File patch.diff added
Attached is an implementation against master....
----------------------------------------
Feature #16468: Switch to Miller-Rabin for Prime.prime?
https://bugs.ruby-lang.org/issues/16468#change-83635
* 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/
^ permalink raw reply [flat|nested] 6+ messages in thread
* [ruby-core:96665] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime?
[not found] <redmine.issue-16468.20191230192711@ruby-lang.org>
2019-12-30 19:27 ` [ruby-core:96600] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime? sblackstone
2020-01-04 19:19 ` [ruby-core:96664] " sblackstone
@ 2020-01-04 23:09 ` ruby-core
2020-01-05 1:23 ` [ruby-core:96667] " sblackstone
` (2 subsequent siblings)
5 siblings, 0 replies; 6+ messages in thread
From: ruby-core @ 2020-01-04 23:09 UTC (permalink / raw)
To: ruby-core
Issue #16468 has been updated by marcandre (Marc-Andre Lafortune).
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?
----------------------------------------
Feature #16468: Switch to Miller-Rabin for Prime.prime?
https://bugs.ruby-lang.org/issues/16468#change-83647
* 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/
^ permalink raw reply [flat|nested] 6+ messages in thread
* [ruby-core:96667] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime?
[not found] <redmine.issue-16468.20191230192711@ruby-lang.org>
` (2 preceding siblings ...)
2020-01-04 23:09 ` [ruby-core:96665] " ruby-core
@ 2020-01-05 1:23 ` sblackstone
2020-01-05 1:41 ` [ruby-core:96668] " mame
2020-01-05 2:05 ` [ruby-core:96669] " sblackstone
5 siblings, 0 replies; 6+ messages in thread
From: sblackstone @ 2020-01-05 1:23 UTC (permalink / raw)
To: ruby-core
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/
^ permalink raw reply [flat|nested] 6+ messages in thread
* [ruby-core:96668] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime?
[not found] <redmine.issue-16468.20191230192711@ruby-lang.org>
` (3 preceding siblings ...)
2020-01-05 1:23 ` [ruby-core:96667] " sblackstone
@ 2020-01-05 1:41 ` mame
2020-01-05 2:05 ` [ruby-core:96669] " sblackstone
5 siblings, 0 replies; 6+ messages in thread
From: mame @ 2020-01-05 1:41 UTC (permalink / raw)
To: ruby-core
Issue #16468 has been updated by mame (Yusuke Endoh).
It can fall back to APR-CL primality test when Miller-Rabin does not work. In my personal opinion, it would be best to keep prime.rb simple because it is a hobby library.
You may be interested in my gem: https://github.com/mame/faster_prime
----------------------------------------
Feature #16468: Switch to Miller-Rabin for Prime.prime?
https://bugs.ruby-lang.org/issues/16468#change-83650
* 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/
^ permalink raw reply [flat|nested] 6+ messages in thread
* [ruby-core:96669] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime?
[not found] <redmine.issue-16468.20191230192711@ruby-lang.org>
` (4 preceding siblings ...)
2020-01-05 1:41 ` [ruby-core:96668] " mame
@ 2020-01-05 2:05 ` sblackstone
5 siblings, 0 replies; 6+ messages in thread
From: sblackstone @ 2020-01-05 2:05 UTC (permalink / raw)
To: ruby-core
Issue #16468 has been updated by steveb3210 (Stephen Blackstone).
On second thought, I think Marc is right, we can't ruin someones day with a composite without a warning that theres a non-zero probability of it being incorrect so I will update......
----------------------------------------
Feature #16468: Switch to Miller-Rabin for Prime.prime?
https://bugs.ruby-lang.org/issues/16468#change-83651
* 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/
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2020-01-05 2:05 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <redmine.issue-16468.20191230192711@ruby-lang.org>
2019-12-30 19:27 ` [ruby-core:96600] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime? sblackstone
2020-01-04 19:19 ` [ruby-core:96664] " sblackstone
2020-01-04 23:09 ` [ruby-core:96665] " ruby-core
2020-01-05 1:23 ` [ruby-core:96667] " sblackstone
2020-01-05 1:41 ` [ruby-core:96668] " mame
2020-01-05 2:05 ` [ruby-core:96669] " sblackstone
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).