forked from josdejong/mathjs
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgcd.js
More file actions
140 lines (131 loc) · 4.1 KB
/
gcd.js
File metadata and controls
140 lines (131 loc) · 4.1 KB
1
2
3
4
5
6
7
8
9
10
11
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
import { isInteger } from '../../utils/number.js'
import { factory } from '../../utils/factory.js'
import { createMod } from './mod.js'
import { createMatAlgo01xDSid } from '../../type/matrix/utils/matAlgo01xDSid.js'
import { createMatAlgo04xSidSid } from '../../type/matrix/utils/matAlgo04xSidSid.js'
import { createMatAlgo10xSids } from '../../type/matrix/utils/matAlgo10xSids.js'
import { createMatrixAlgorithmSuite } from '../../type/matrix/utils/matrixAlgorithmSuite.js'
import { ArgumentsError } from '../../error/ArgumentsError.js'
const name = 'gcd'
const dependencies = [
'typed',
'config',
'round',
'matrix',
'equalScalar',
'zeros',
'BigNumber',
'DenseMatrix',
'concat'
]
const gcdTypes = 'number | BigNumber | Fraction | Matrix | Array'
const gcdManyTypesSignature = `${gcdTypes}, ${gcdTypes}, ...${gcdTypes}`
function is1d (array) {
return !array.some(element => Array.isArray(element))
}
export const createGcd = /* #__PURE__ */ factory(name, dependencies, ({ typed, matrix, config, round, equalScalar, zeros, BigNumber, DenseMatrix, concat }) => {
const mod = createMod({ typed, config, round, matrix, equalScalar, zeros, DenseMatrix, concat })
const matAlgo01xDSid = createMatAlgo01xDSid({ typed })
const matAlgo04xSidSid = createMatAlgo04xSidSid({ typed, equalScalar })
const matAlgo10xSids = createMatAlgo10xSids({ typed, DenseMatrix })
const matrixAlgorithmSuite = createMatrixAlgorithmSuite({ typed, matrix, concat })
/**
* Calculate the greatest common divisor for two or more values or arrays.
*
* For matrices, the function is evaluated element wise.
*
* Syntax:
*
* math.gcd(a, b)
* math.gcd(a, b, c, ...)
*
* Examples:
*
* math.gcd(8, 12) // returns 4
* math.gcd(-4, 6) // returns 2
* math.gcd(25, 15, -10) // returns 5
*
* math.gcd([8, -4], [12, 6]) // returns [4, 2]
*
* See also:
*
* lcm, xgcd
*
* @param {... number | BigNumber | Fraction | Array | Matrix} args Two or more integer numbers
* @return {number | BigNumber | Fraction | Array | Matrix} The greatest common divisor
*/
return typed(
name,
{
'number, number': _gcdNumber,
'BigNumber, BigNumber': _gcdBigNumber,
'Fraction, Fraction': (x, y) => x.gcd(y)
},
matrixAlgorithmSuite({
SS: matAlgo04xSidSid,
DS: matAlgo01xDSid,
Ss: matAlgo10xSids
}),
{
[gcdManyTypesSignature]: typed.referToSelf(self => (a, b, args) => {
let res = self(a, b)
for (let i = 0; i < args.length; i++) {
res = self(res, args[i])
}
return res
}),
Array: typed.referToSelf(self => (array) => {
if (array.length === 1 && Array.isArray(array[0]) && is1d(array[0])) {
return self(...array[0])
}
if (is1d(array)) {
return self(...array)
}
throw new ArgumentsError('gcd() supports only 1d matrices!')
}),
Matrix: typed.referToSelf(self => (matrix) => {
return self(matrix.toArray())
})
}
)
/**
* Calculate gcd for numbers
* @param {number} a
* @param {number} b
* @returns {number} Returns the greatest common denominator of a and b
* @private
*/
function _gcdNumber (a, b) {
if (!isInteger(a) || !isInteger(b)) {
throw new Error('Parameters in function gcd must be integer numbers')
}
// https://en.wikipedia.org/wiki/Euclidean_algorithm
let r
while (b !== 0) {
r = mod(a, b)
a = b
b = r
}
return (a < 0) ? -a : a
}
/**
* Calculate gcd for BigNumbers
* @param {BigNumber} a
* @param {BigNumber} b
* @returns {BigNumber} Returns greatest common denominator of a and b
* @private
*/
function _gcdBigNumber (a, b) {
if (!a.isInt() || !b.isInt()) {
throw new Error('Parameters in function gcd must be integer numbers')
}
// https://en.wikipedia.org/wiki/Euclidean_algorithm
const zero = new BigNumber(0)
while (!b.isZero()) {
const r = mod(a, b)
a = b
b = r
}
return a.lt(zero) ? a.neg() : a
}
})