simple-squiggle

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

isPrime.js (4147B)

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