simple-squiggle

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

xgcd.js (2613B)

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