1 | import { factory } from '../../utils/factory';
|
2 | import { xgcdNumber } from '../../plain/number';
|
3 | var name = 'xgcd';
|
4 | var dependencies = ['typed', 'config', 'matrix', 'BigNumber'];
|
5 | export var createXgcd =
|
6 |
|
7 | factory(name, dependencies, function (_ref) {
|
8 | var typed = _ref.typed,
|
9 | config = _ref.config,
|
10 | matrix = _ref.matrix,
|
11 | BigNumber = _ref.BigNumber;
|
12 |
|
13 | |
14 |
|
15 |
|
16 |
|
17 |
|
18 |
|
19 |
|
20 |
|
21 |
|
22 |
|
23 |
|
24 |
|
25 |
|
26 |
|
27 |
|
28 |
|
29 |
|
30 |
|
31 |
|
32 |
|
33 |
|
34 |
|
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
|
42 |
|
43 | });
|
44 | |
45 |
|
46 |
|
47 |
|
48 |
|
49 |
|
50 |
|
51 |
|
52 | function _xgcdBigNumber(a, b) {
|
53 |
|
54 | var
|
55 | t;
|
56 | var
|
57 | q;
|
58 | var
|
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 | }); |
\ | No newline at end of file |