Project

General

Profile

Feature #16468

Switch to Miller-Rabin for Prime.prime?

Added by steveb3210 (Stephen Blackstone) 11 months ago. Updated 9 months ago.

Status:
Open
Priority:
Normal
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
#1

Updated by steveb3210 (Stephen Blackstone) 11 months ago

  • Description updated (diff)

Updated by steveb3210 (Stephen Blackstone) 11 months ago

  • File patch.diff added

Attached is an implementation against master....

Updated by marcandre (Marc-Andre Lafortune) 11 months 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) 11 months 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) 11 months 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) 11 months 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) 9 months ago

  • File patch_with_argument_error.diff added
#8

Updated by steveb3210 (Stephen Blackstone) 9 months ago

  • File deleted (patch.diff)

Updated by steveb3210 (Stephen Blackstone) 9 months ago

  • File patch_with_argument_error.diff added
#10

Updated by steveb3210 (Stephen Blackstone) 9 months ago

  • File deleted (patch_with_argument_error.diff)

Updated by steveb3210 (Stephen Blackstone) 9 months ago

  • File patch_with_argument_error_and_tests.diff added
#12

Updated by steveb3210 (Stephen Blackstone) 9 months ago

  • File deleted (patch_with_argument_error.diff)
#13

Updated by steveb3210 (Stephen Blackstone) 9 months ago

  • File deleted (patch_with_argument_error_and_tests.diff)

Updated by steveb3210 (Stephen Blackstone) 9 months ago

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

Updated by Dan0042 (Daniel DeLorme) 9 months 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) 9 months 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.

#17

Updated by steveb3210 (Stephen Blackstone) 9 months ago

  • File deleted (patch_with_argument_error_and_tests.diff)

Updated by steveb3210 (Stephen Blackstone) 9 months ago

Attached is the latest diff.

Updated by Dan0042 (Daniel DeLorme) 9 months 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.

Also available in: Atom PDF