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