Anonymous user
Chinese remainder theorem: Difference between revisions
Adding JS
(fixed Julia example for larger numbers) |
(Adding JS) |
||
Line 1,129:
<pre>23</pre>
=={{header|JavaScript}}==
<lang javascript>
function crt(num, rem) {
let sum = 0;
const prod = num.reduce((a, c) => a * c, 1);
for (let i = 0; i < num.length; i++) {
const [ni, ri] = [num[i], rem[i]];
const p = Math.floor(prod / ni);
sum += ri * p * mulInv(p, ni);
}
return sum % prod;
}
function mulInv(a, b) {
const b0 = b;
let [x0, x1] = [0, 1];
if (b === 1) {
return 1;
}
while (a > 1) {
const q = Math.floor(a / b);
[a, b] = [b, a % b];
[x0, x1] = [x1 - q * x0, x0];
}
if (x1 < 0) {
x1 += b0;
}
return x1;
}
console.log(crt([3,5,7], [2,3,2]))</lang>
'''Output:'''
<pre>
23
</pre>
=={{header|jq}}==
| |||