simple-squiggle

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

gcd.js (4726B)

      1 import { factory } from '../../utils/factory.js';
      2 import { createAlgorithm01 } from '../../type/matrix/utils/algorithm01.js';
      3 import { createAlgorithm04 } from '../../type/matrix/utils/algorithm04.js';
      4 import { createAlgorithm10 } from '../../type/matrix/utils/algorithm10.js';
      5 import { createAlgorithm13 } from '../../type/matrix/utils/algorithm13.js';
      6 import { createAlgorithm14 } from '../../type/matrix/utils/algorithm14.js';
      7 import { gcdNumber } from '../../plain/number/index.js';
      8 var name = 'gcd';
      9 var dependencies = ['typed', 'matrix', 'equalScalar', 'BigNumber', 'DenseMatrix'];
     10 export var createGcd = /* #__PURE__ */factory(name, dependencies, _ref => {
     11   var {
     12     typed,
     13     matrix,
     14     equalScalar,
     15     BigNumber,
     16     DenseMatrix
     17   } = _ref;
     18   var algorithm01 = createAlgorithm01({
     19     typed
     20   });
     21   var algorithm04 = createAlgorithm04({
     22     typed,
     23     equalScalar
     24   });
     25   var algorithm10 = createAlgorithm10({
     26     typed,
     27     DenseMatrix
     28   });
     29   var algorithm13 = createAlgorithm13({
     30     typed
     31   });
     32   var algorithm14 = createAlgorithm14({
     33     typed
     34   });
     35   /**
     36    * Calculate the greatest common divisor for two or more values or arrays.
     37    *
     38    * For matrices, the function is evaluated element wise.
     39    *
     40    * Syntax:
     41    *
     42    *    math.gcd(a, b)
     43    *    math.gcd(a, b, c, ...)
     44    *
     45    * Examples:
     46    *
     47    *    math.gcd(8, 12)              // returns 4
     48    *    math.gcd(-4, 6)              // returns 2
     49    *    math.gcd(25, 15, -10)        // returns 5
     50    *
     51    *    math.gcd([8, -4], [12, 6])   // returns [4, 2]
     52    *
     53    * See also:
     54    *
     55    *    lcm, xgcd
     56    *
     57    * @param {... number | BigNumber | Fraction | Array | Matrix} args  Two or more integer numbers
     58    * @return {number | BigNumber | Fraction | Array | Matrix}                           The greatest common divisor
     59    */
     60 
     61   return typed(name, {
     62     'number, number': gcdNumber,
     63     'BigNumber, BigNumber': _gcdBigNumber,
     64     'Fraction, Fraction': function FractionFraction(x, y) {
     65       return x.gcd(y);
     66     },
     67     'SparseMatrix, SparseMatrix': function SparseMatrixSparseMatrix(x, y) {
     68       return algorithm04(x, y, this);
     69     },
     70     'SparseMatrix, DenseMatrix': function SparseMatrixDenseMatrix(x, y) {
     71       return algorithm01(y, x, this, true);
     72     },
     73     'DenseMatrix, SparseMatrix': function DenseMatrixSparseMatrix(x, y) {
     74       return algorithm01(x, y, this, false);
     75     },
     76     'DenseMatrix, DenseMatrix': function DenseMatrixDenseMatrix(x, y) {
     77       return algorithm13(x, y, this);
     78     },
     79     'Array, Array': function ArrayArray(x, y) {
     80       // use matrix implementation
     81       return this(matrix(x), matrix(y)).valueOf();
     82     },
     83     'Array, Matrix': function ArrayMatrix(x, y) {
     84       // use matrix implementation
     85       return this(matrix(x), y);
     86     },
     87     'Matrix, Array': function MatrixArray(x, y) {
     88       // use matrix implementation
     89       return this(x, matrix(y));
     90     },
     91     'SparseMatrix, number | BigNumber': function SparseMatrixNumberBigNumber(x, y) {
     92       return algorithm10(x, y, this, false);
     93     },
     94     'DenseMatrix, number | BigNumber': function DenseMatrixNumberBigNumber(x, y) {
     95       return algorithm14(x, y, this, false);
     96     },
     97     'number | BigNumber, SparseMatrix': function numberBigNumberSparseMatrix(x, y) {
     98       return algorithm10(y, x, this, true);
     99     },
    100     'number | BigNumber, DenseMatrix': function numberBigNumberDenseMatrix(x, y) {
    101       return algorithm14(y, x, this, true);
    102     },
    103     'Array, number | BigNumber': function ArrayNumberBigNumber(x, y) {
    104       // use matrix implementation
    105       return algorithm14(matrix(x), y, this, false).valueOf();
    106     },
    107     'number | BigNumber, Array': function numberBigNumberArray(x, y) {
    108       // use matrix implementation
    109       return algorithm14(matrix(y), x, this, true).valueOf();
    110     },
    111     // TODO: need a smarter notation here
    112     'Array | Matrix | number | BigNumber, Array | Matrix | number | BigNumber, ...Array | Matrix | number | BigNumber': function ArrayMatrixNumberBigNumberArrayMatrixNumberBigNumberArrayMatrixNumberBigNumber(a, b, args) {
    113       var res = this(a, b);
    114 
    115       for (var i = 0; i < args.length; i++) {
    116         res = this(res, args[i]);
    117       }
    118 
    119       return res;
    120     }
    121   });
    122   /**
    123    * Calculate gcd for BigNumbers
    124    * @param {BigNumber} a
    125    * @param {BigNumber} b
    126    * @returns {BigNumber} Returns greatest common denominator of a and b
    127    * @private
    128    */
    129 
    130   function _gcdBigNumber(a, b) {
    131     if (!a.isInt() || !b.isInt()) {
    132       throw new Error('Parameters in function gcd must be integer numbers');
    133     } // https://en.wikipedia.org/wiki/Euclidean_algorithm
    134 
    135 
    136     var zero = new BigNumber(0);
    137 
    138     while (!b.isZero()) {
    139       var r = a.mod(b);
    140       a = b;
    141       b = r;
    142     }
    143 
    144     return a.lt(zero) ? a.neg() : a;
    145   }
    146 });