simple-squiggle

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

xgcd.js (2399B)

      1 import { factory } from '../../utils/factory.js';
      2 import { xgcdNumber } from '../../plain/number/index.js';
      3 var name = 'xgcd';
      4 var dependencies = ['typed', 'config', 'matrix', 'BigNumber'];
      5 export var createXgcd = /* #__PURE__ */factory(name, dependencies, _ref => {
      6   var {
      7     typed,
      8     config,
      9     matrix,
     10     BigNumber
     11   } = _ref;
     12 
     13   /**
     14    * Calculate the extended greatest common divisor for two values.
     15    * See https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm.
     16    *
     17    * Syntax:
     18    *
     19    *    math.xgcd(a, b)
     20    *
     21    * Examples:
     22    *
     23    *    math.xgcd(8, 12)             // returns [4, -1, 1]
     24    *    math.gcd(8, 12)              // returns 4
     25    *    math.xgcd(36163, 21199)      // returns [1247, -7, 12]
     26    *
     27    * See also:
     28    *
     29    *    gcd, lcm
     30    *
     31    * @param {number | BigNumber} a  An integer number
     32    * @param {number | BigNumber} b  An integer number
     33    * @return {Array}              Returns an array containing 3 integers `[div, m, n]`
     34    *                              where `div = gcd(a, b)` and `a*m + b*n = div`
     35    */
     36   return typed(name, {
     37     'number, number': function numberNumber(a, b) {
     38       var res = xgcdNumber(a, b);
     39       return config.matrix === 'Array' ? res : matrix(res);
     40     },
     41     'BigNumber, BigNumber': _xgcdBigNumber // TODO: implement support for Fraction
     42 
     43   });
     44   /**
     45    * Calculate xgcd for two BigNumbers
     46    * @param {BigNumber} a
     47    * @param {BigNumber} b
     48    * @return {BigNumber[]} result
     49    * @private
     50    */
     51 
     52   function _xgcdBigNumber(a, b) {
     53     // source: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
     54     var // used to swap two variables
     55     t;
     56     var // quotient
     57     q;
     58     var // remainder
     59     r;
     60     var zero = new BigNumber(0);
     61     var one = new BigNumber(1);
     62     var x = zero;
     63     var lastx = one;
     64     var y = one;
     65     var lasty = zero;
     66 
     67     if (!a.isInt() || !b.isInt()) {
     68       throw new Error('Parameters in function xgcd must be integer numbers');
     69     }
     70 
     71     while (!b.isZero()) {
     72       q = a.div(b).floor();
     73       r = a.mod(b);
     74       t = x;
     75       x = lastx.minus(q.times(x));
     76       lastx = t;
     77       t = y;
     78       y = lasty.minus(q.times(y));
     79       lasty = t;
     80       a = b;
     81       b = r;
     82     }
     83 
     84     var res;
     85 
     86     if (a.lt(zero)) {
     87       res = [a.neg(), lastx.neg(), lasty.neg()];
     88     } else {
     89       res = [a, !a.isZero() ? lastx : 0, lasty];
     90     }
     91 
     92     return config.matrix === 'Array' ? res : matrix(res);
     93   }
     94 });