Project

General

Profile

Actions

Feature #16468

closed

Switch to Miller-Rabin for Prime.prime?

Added by steveb3210 (Stephen Blackstone) almost 5 years ago. Updated about 4 years ago.

Status:
Closed
Assignee:
-
Target version:
-
[ruby-core:96600]

Description

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

prime_patch.diff (2.5 KB) prime_patch.diff steveb3210 (Stephen Blackstone), 02/20/2020 07:19 PM
Actions #1

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

  • Description updated (diff)

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

  • File patch.diff added

Attached is an implementation against master....

Updated by marcandre (Marc-Andre Lafortune) almost 5 years ago

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?

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

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.

Updated by mame (Yusuke Endoh) almost 5 years ago

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

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

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

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

  • File patch_with_argument_error.diff added
Actions #8

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

  • File deleted (patch.diff)

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

  • File patch_with_argument_error.diff added
Actions #10

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

  • File deleted (patch_with_argument_error.diff)

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

  • File patch_with_argument_error_and_tests.diff added
Actions #12

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

  • File deleted (patch_with_argument_error.diff)
Actions #13

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

  • File deleted (patch_with_argument_error_and_tests.diff)

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

  • File patch_with_argument_error_and_tests.diff added
  • Add bounds check
  • Add test

Updated by Dan0042 (Daniel DeLorme) almost 5 years ago

I think it would be interesting to expose the algorithm for larger numbers. So you could have miller_rabin which allows any integer, and prime? which checks the value and either call miller_rabin or raise ArgumentError.

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

Dan0042 (Daniel DeLorme) wrote in #note-15:

I think it would be interesting to expose the algorithm for larger numbers. So you could have miller_rabin which allows any integer, and prime? which checks the value and either call miller_rabin or raise ArgumentError.

Unforunately Miller-Rabin is not a deterministic test for arbitrarily large n - its only the work in the paper https://arxiv.org/pdf/1509.00864.pdf that allows us to provide functionality up to a bound.

Actions #17

Updated by steveb3210 (Stephen Blackstone) almost 5 years ago

  • File deleted (patch_with_argument_error_and_tests.diff)

Updated by Dan0042 (Daniel DeLorme) almost 5 years ago

steveb3210 (Stephen Blackstone) wrote in #note-16:

Unforunately Miller-Rabin is not a deterministic test for arbitrarily large n - its only the work in the paper https://arxiv.org/pdf/1509.00864.pdf that allows us to provide functionality up to a bound.

Yes, I know, that was my point. Maybe I want to know if arbitrarily large N is prime while accepting a probability of error of 4**(-k); then I could use miller_rabin(k). And the prime? method uses a bounds check and miller_rabin(13) to produce a deterministic result.

BTW your implementation appears to be off by one. It should be: if self >= 3317044064679887385961981 then raise ArgumentError. You could also slightly reduce the runtime for small numbers by using return list.include?(self) if self <= list.last before the loop, instead of checking inside the loop.

Actions #20

Updated by Anonymous about 4 years ago

  • Status changed from Open to Closed

Applied in changeset git|1866d483dce614a02c5186bd0588b48a5041e55e.


[ruby/prime] Optimize Integer#prime?

Miller Rabin algorithm can be used to test primality for integers smaller than a max value "MaxMR" (~3e24)

It can be much faster than previous implementation: ~100x faster for numbers with 13 digits, at least 5 orders of magnitude for even larger numbers (previous implementation is so slow that it requires more patience than I have for more precise estimate).

Miller Rabin test becomes faster than previous implementation at somewhere in the range 1e5-1e6. It seems that the range 62000..66000 is where Miller Rabin starts being always faster, so I picked 0xffff arbitrarily; before that, or above "MaxMR", the previous implementation remains.

I compared the faster_prime gem too. It is slower than previous implementation up to ~1e4. After that it becomes faster and faster compared to previous implementation, but is still slower than Miller Rabin starting at ~1e5 and up to MaxMR. Thus, after this commit, builtin Integer#prime? will be similar or faster than faster_prime up to "MaxMR".

Adapted from patch of Stephen Blackstone [Feature #16468]

Benchmark results and code: https://gist.github.com/marcandre/b263bdae488e76dabdda84daf73733b9

Co-authored-by: Stephen Blackstone

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0