simple-squiggle

A restricted subset of Squiggle
Log | Files | Refs | README

isPrime.js (3924B)

      1 import { deepMap } from '../../utils/collection.js';
      2 import { factory } from '../../utils/factory.js';
      3 var name = 'isPrime';
      4 var dependencies = ['typed'];
      5 export var createIsPrime = /* #__PURE__ */factory(name, dependencies, _ref => {
      6   var {
      7     typed
      8   } = _ref;
      9 
     10   /**
     11    * Test whether a value is prime: has no divisors other than itself and one.
     12    * The function supports type `number`, `bignumber`.
     13    *
     14    * The function is evaluated element-wise in case of Array or Matrix input.
     15    *
     16    * Syntax:
     17    *
     18    *     math.isPrime(x)
     19    *
     20    * Examples:
     21    *
     22    *    math.isPrime(3)                     // returns true
     23    *    math.isPrime(-2)                    // returns false
     24    *    math.isPrime(0)                     // returns false
     25    *    math.isPrime(-0)                    // returns false
     26    *    math.isPrime(0.5)                   // returns false
     27    *    math.isPrime('2')                   // returns true
     28    *    math.isPrime([2, 17, 100])           // returns [true, true, false]
     29    *
     30    * See also:
     31    *
     32    *    isNumeric, isZero, isNegative, isInteger
     33    *
     34    * @param {number | BigNumber | Array | Matrix} x  Value to be tested
     35    * @return {boolean}  Returns true when `x` is larger than zero.
     36    *                    Throws an error in case of an unknown data type.
     37    */
     38   return typed(name, {
     39     number: function number(x) {
     40       if (x * 0 !== 0) {
     41         return false;
     42       }
     43 
     44       if (x <= 3) {
     45         return x > 1;
     46       }
     47 
     48       if (x % 2 === 0 || x % 3 === 0) {
     49         return false;
     50       }
     51 
     52       for (var i = 5; i * i <= x; i += 6) {
     53         if (x % i === 0 || x % (i + 2) === 0) {
     54           return false;
     55         }
     56       }
     57 
     58       return true;
     59     },
     60     BigNumber: function BigNumber(n) {
     61       if (n.toNumber() * 0 !== 0) {
     62         return false;
     63       }
     64 
     65       if (n.lte(3)) return n.gt(1);
     66       if (n.mod(2).eq(0) || n.mod(3).eq(0)) return false;
     67 
     68       if (n.lt(Math.pow(2, 32))) {
     69         var x = n.toNumber();
     70 
     71         for (var i = 5; i * i <= x; i += 6) {
     72           if (x % i === 0 || x % (i + 2) === 0) {
     73             return false;
     74           }
     75         }
     76 
     77         return true;
     78       }
     79 
     80       function modPow(base, exponent, modulus) {
     81         // exponent can be huge, use non-recursive variant
     82         var accumulator = 1;
     83 
     84         while (!exponent.eq(0)) {
     85           if (exponent.mod(2).eq(0)) {
     86             exponent = exponent.div(2);
     87             base = base.mul(base).mod(modulus);
     88           } else {
     89             exponent = exponent.sub(1);
     90             accumulator = base.mul(accumulator).mod(modulus);
     91           }
     92         }
     93 
     94         return accumulator;
     95       } // https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants
     96 
     97 
     98       var Decimal = n.constructor.clone({
     99         precision: n.toFixed(0).length * 2
    100       });
    101       n = new Decimal(n);
    102       var r = 0;
    103       var d = n.sub(1);
    104 
    105       while (d.mod(2).eq(0)) {
    106         d = d.div(2);
    107         r += 1;
    108       }
    109 
    110       var bases = null; // https://en.wikipedia.org/wiki/Miller–Rabin_primality_test#Testing_against_small_sets_of_bases
    111 
    112       if (n.lt('3317044064679887385961981')) {
    113         bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41].filter(x => x < n);
    114       } else {
    115         var max = Math.min(n.toNumber() - 2, Math.floor(2 * Math.pow(n.toFixed(0).length * Math.log(10), 2)));
    116         bases = [];
    117 
    118         for (var _i = 2; _i <= max; _i += 1) {
    119           bases.push(max);
    120         }
    121       }
    122 
    123       for (var _i2 = 0; _i2 < bases.length; _i2 += 1) {
    124         var a = bases[_i2];
    125         var adn = modPow(n.sub(n).add(a), d, n);
    126 
    127         if (!adn.eq(1)) {
    128           for (var _i3 = 0, _x = adn; !_x.eq(n.sub(1)); _i3 += 1, _x = _x.mul(_x).mod(n)) {
    129             if (_i3 === r - 1) {
    130               return false;
    131             }
    132           }
    133         }
    134       }
    135 
    136       return true;
    137     },
    138     'Array | Matrix': function ArrayMatrix(x) {
    139       return deepMap(x, this);
    140     }
    141   });
    142 });