Chinese remainder theorem: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,129: / 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>
+</pre>
 =={{header|jq}}==