Mercurial > octave
changeset 31051:5f015f2829b7
maint: Merge stable to default
author | Arun Giridhar <arungiridhar@gmail.com> |
---|---|
date | Wed, 01 Jun 2022 17:20:22 -0400 |
parents | d5997bbdb641 (current diff) 3a93a77dd4cf (diff) |
children | 34cfde95c5fa |
files | libinterp/corefcn/__isprimelarge__.cc scripts/specfun/isprime.m |
diffstat | 2 files changed, 14 insertions(+), 24 deletions(-) [+] |
line wrap: on
line diff
--- a/libinterp/corefcn/__isprimelarge__.cc Tue May 31 23:34:23 2022 -0400 +++ b/libinterp/corefcn/__isprimelarge__.cc Wed Jun 01 17:20:22 2022 -0400 @@ -116,20 +116,12 @@ // If the number passes all 12 tests, then it is prime. // If it fails any, then it is composite. // The first 12 primes suffice to test all 64-bit integers. - if (! millerrabin ( 2, d, r, n)) return false; - if (! millerrabin ( 3, d, r, n)) return false; - if (! millerrabin ( 5, d, r, n)) return false; - if (! millerrabin ( 7, d, r, n)) return false; - if (! millerrabin (11, d, r, n)) return false; - if (! millerrabin (13, d, r, n)) return false; - if (! millerrabin (17, d, r, n)) return false; - if (! millerrabin (19, d, r, n)) return false; - if (! millerrabin (23, d, r, n)) return false; - if (! millerrabin (29, d, r, n)) return false; - if (! millerrabin (31, d, r, n)) return false; - if (! millerrabin (37, d, r, n)) return false; - // If we are all the way here, then it is prime. - return true; + return millerrabin ( 2, d, r, n) && millerrabin ( 3, d, r, n) + && millerrabin ( 5, d, r, n) && millerrabin ( 7, d, r, n) + && millerrabin (11, d, r, n) && millerrabin (13, d, r, n) + && millerrabin (17, d, r, n) && millerrabin (19, d, r, n) + && millerrabin (23, d, r, n) && millerrabin (29, d, r, n) + && millerrabin (31, d, r, n) && millerrabin (37, d, r, n); /* Mathematical references for the curious as to why we need only
--- a/scripts/specfun/isprime.m Tue May 31 23:34:23 2022 -0400 +++ b/scripts/specfun/isprime.m Wed Jun 01 17:20:22 2022 -0400 @@ -103,21 +103,19 @@ pr = [2 3 5 7 11 13 17 19 23 29 31 37]; tf = lookup (pr, x, "b"); # quick search for table matches. - THRESHOLD = 29e9; + THRESHOLD = 195e8; ## FIXME: THRESHOLD is the input value at which Miller-Rabin ## becomes more efficient than direct division. For smaller numbers, ## use direct division. For larger numbers, use Miller-Rabin. ## - ## From numerical experiments in Oct 2021, this was observed: + ## From numerical experiments in Jun 2022, this was observed: ## THRESHOLD Division Miller-Rabin - ## 380e9 75.0466s 30.868s - ## 100e9 45.0874s 29.1794s - ## 10e9 18.5075s 25.4392s - ## 50e9 31.6317s 27.7251s - ## 25e9 25.1215s 27.004s - ## 38e9 31.4674s 28.1336s - ## 30e9 28.3848s 27.9982s - ## which is close enough to interpolate, so final threshold = 29 billion. + ## 29e9 29.8196s 26.2484s (previous value) + ## 20e9 26.7445s 26.0161s + ## 10e9 20.9330s 25.3247s + ## 19e9 26.5397s 26.8987s + ## 195e8 26.5735s 26.4749s + ## which is close enough, so new threshold = 195e8. ## ## The test code was this: ## n = THRESHOLD - (1:1e7); tic; isprime(n); toc