Mercurial > octave
changeset 30352:08f6bbd3ed23
maint: Merge stable to default.
author | Kai T. Ohlhus <k.ohlhus@gmail.com> |
---|---|
date | Thu, 25 Nov 2021 14:33:32 +0900 |
parents | e27be169feff (current diff) 4f4fa00edada (diff) |
children | 045d93c84fe7 |
files | libinterp/corefcn/__isprimelarge__.cc |
diffstat | 1 files changed, 12 insertions(+), 10 deletions(-) [+] |
line wrap: on
line diff
--- a/libinterp/corefcn/__isprimelarge__.cc Wed Nov 24 13:19:49 2021 -0500 +++ b/libinterp/corefcn/__isprimelarge__.cc Thu Nov 25 14:33:32 2021 +0900 @@ -27,14 +27,13 @@ #include "error.h" #include "ovl.h" -#include <iostream> - OCTAVE_NAMESPACE_BEGIN // This function implements the Schrage technique for modular multiplication. // The returned value is equivalent to "mod (a*b, modulus)" // but calculated without overflow. -uint64_t safemultiply (uint64_t a, uint64_t b, uint64_t modulus) +uint64_t +safemultiply (uint64_t a, uint64_t b, uint64_t modulus) { if (! a || ! b) return 0; @@ -58,7 +57,8 @@ // This function returns "mod (a^b, modulus)" // but calculated without overflow. -uint64_t safepower (uint64_t a, uint64_t b, uint64_t modulus) +uint64_t +safepower (uint64_t a, uint64_t b, uint64_t modulus) { uint64_t retval = 1; while (b > 0) @@ -73,7 +73,8 @@ // This function implements a single round of Miller-Rabin primality testing. // Returns false if composite, true if pseudoprime for this divisor. -bool millerrabin (uint64_t div, uint64_t d, uint64_t r, uint64_t n) +bool +millerrabin (uint64_t div, uint64_t d, uint64_t r, uint64_t n) { uint64_t x = safepower (div, d, n); if (x == 1 || x == n-1) @@ -90,7 +91,8 @@ // This function uses the Miller-Rabin test to find out whether the input is // prime or composite. The input is required to be a scalar 64-bit integer. -bool isprimescalar (uint64_t n) +bool +isprimescalar (uint64_t n) { // Fast return for even numbers. // n==2 is excluded by the time this function is called. @@ -101,10 +103,10 @@ uint64_t d = n-1; uint64_t r = 0; while (! (d & 1)) - { - d >>= 1; - r++; - } + { + d >>= 1; + r++; + } // Miller-Rabin test with the first 12 primes. // If the number passes all 12 tests, then it is prime.