Mercurial > jwe > octave
comparison libinterp/corefcn/__isprimelarge__.cc @ 31055:3a93a77dd4cf stable
Minor performance tweaks to isprime.m and __isprimelarge__.cc
__isprimelarge__.cc: change an if-else ladder to a single equivalent
return statement, about 1% faster and less code.
isprime.m: periodic check and retune of internal threshold parameter
used to select one technique over the other.
| author | Arun Giridhar <arungiridhar@gmail.com> |
|---|---|
| date | Wed, 01 Jun 2022 17:19:30 -0400 |
| parents | cfade47fc4fc |
| children | 5f015f2829b7 |
comparison
equal
deleted
inserted
replaced
| 31052:1589a7967d1e | 31055:3a93a77dd4cf |
|---|---|
| 113 | 113 |
| 114 // Miller-Rabin test with the first 12 primes. | 114 // Miller-Rabin test with the first 12 primes. |
| 115 // If the number passes all 12 tests, then it is prime. | 115 // If the number passes all 12 tests, then it is prime. |
| 116 // If it fails any, then it is composite. | 116 // If it fails any, then it is composite. |
| 117 // The first 12 primes suffice to test all 64-bit integers. | 117 // The first 12 primes suffice to test all 64-bit integers. |
| 118 if (! millerrabin ( 2, d, r, n)) return false; | 118 return millerrabin ( 2, d, r, n) && millerrabin ( 3, d, r, n) |
| 119 if (! millerrabin ( 3, d, r, n)) return false; | 119 && millerrabin ( 5, d, r, n) && millerrabin ( 7, d, r, n) |
| 120 if (! millerrabin ( 5, d, r, n)) return false; | 120 && millerrabin (11, d, r, n) && millerrabin (13, d, r, n) |
| 121 if (! millerrabin ( 7, d, r, n)) return false; | 121 && millerrabin (17, d, r, n) && millerrabin (19, d, r, n) |
| 122 if (! millerrabin (11, d, r, n)) return false; | 122 && millerrabin (23, d, r, n) && millerrabin (29, d, r, n) |
| 123 if (! millerrabin (13, d, r, n)) return false; | 123 && millerrabin (31, d, r, n) && millerrabin (37, d, r, n); |
| 124 if (! millerrabin (17, d, r, n)) return false; | |
| 125 if (! millerrabin (19, d, r, n)) return false; | |
| 126 if (! millerrabin (23, d, r, n)) return false; | |
| 127 if (! millerrabin (29, d, r, n)) return false; | |
| 128 if (! millerrabin (31, d, r, n)) return false; | |
| 129 if (! millerrabin (37, d, r, n)) return false; | |
| 130 // If we are all the way here, then it is prime. | |
| 131 return true; | |
| 132 | 124 |
| 133 /* | 125 /* |
| 134 Mathematical references for the curious as to why we need only | 126 Mathematical references for the curious as to why we need only |
| 135 the 12 smallest primes for testing all 64-bit numbers: | 127 the 12 smallest primes for testing all 64-bit numbers: |
| 136 (1) https://oeis.org/A014233 | 128 (1) https://oeis.org/A014233 |