Add iterative version of Euclidean algorithm.

trekhleb · trekhleb · commit 2451db975dc4 · 2018-09-18T08:17:47.000+03:00
diff --git a/src/algorithms/math/euclidean-algorithm/__test__/euclideanAlgorithm.test.js b/src/algorithms/math/euclidean-algorithm/__test__/euclideanAlgorithm.test.js
@@ -1,7 +1,7 @@
 import euclideanAlgorithm from '../euclideanAlgorithm';
 
 describe('euclideanAlgorithm', () => {
-  it('should calculate GCD', () => {
+  it('should calculate GCD recursively', () => {
     expect(euclideanAlgorithm(0, 0)).toBe(0);
     expect(euclideanAlgorithm(2, 0)).toBe(2);
     expect(euclideanAlgorithm(0, 2)).toBe(2);
diff --git a/src/algorithms/math/euclidean-algorithm/__test__/euclideanAlgorithmIterative.test.js b/src/algorithms/math/euclidean-algorithm/__test__/euclideanAlgorithmIterative.test.js
@@ -0,0 +1,26 @@
+import euclideanAlgorithmIterative from '../euclideanAlgorithmIterative';
+
+describe('euclideanAlgorithmIterative', () => {
+  it('should calculate GCD iteratively', () => {
+    expect(euclideanAlgorithmIterative(0, 0)).toBe(0);
+    expect(euclideanAlgorithmIterative(2, 0)).toBe(2);
+    expect(euclideanAlgorithmIterative(0, 2)).toBe(2);
+    expect(euclideanAlgorithmIterative(1, 2)).toBe(1);
+    expect(euclideanAlgorithmIterative(2, 1)).toBe(1);
+    expect(euclideanAlgorithmIterative(6, 6)).toBe(6);
+    expect(euclideanAlgorithmIterative(2, 4)).toBe(2);
+    expect(euclideanAlgorithmIterative(4, 2)).toBe(2);
+    expect(euclideanAlgorithmIterative(12, 4)).toBe(4);
+    expect(euclideanAlgorithmIterative(4, 12)).toBe(4);
+    expect(euclideanAlgorithmIterative(5, 13)).toBe(1);
+    expect(euclideanAlgorithmIterative(27, 13)).toBe(1);
+    expect(euclideanAlgorithmIterative(24, 60)).toBe(12);
+    expect(euclideanAlgorithmIterative(60, 24)).toBe(12);
+    expect(euclideanAlgorithmIterative(252, 105)).toBe(21);
+    expect(euclideanAlgorithmIterative(105, 252)).toBe(21);
+    expect(euclideanAlgorithmIterative(1071, 462)).toBe(21);
+    expect(euclideanAlgorithmIterative(462, 1071)).toBe(21);
+    expect(euclideanAlgorithmIterative(462, -1071)).toBe(21);
+    expect(euclideanAlgorithmIterative(-462, -1071)).toBe(21);
+  });
+});
diff --git a/src/algorithms/math/euclidean-algorithm/euclideanAlgorithm.js b/src/algorithms/math/euclidean-algorithm/euclideanAlgorithm.js
@@ -1,25 +1,15 @@
 /**
+ * Recursive version of Euclidean Algorithm of finding greatest common divisor (GCD).
  * @param {number} originalA
  * @param {number} originalB
  * @return {number}
  */
-
-/*Method 1: A bit Complex to understand*/
 export default function euclideanAlgorithm(originalA, originalB) {
+  // Make input numbers positive.
   const a = Math.abs(originalA);
   const b = Math.abs(originalB);
 
+  // To make algorithm work faster instead of subtracting one number from the other
+  // we may use modulo operation.
   return (b === 0) ? a : euclideanAlgorithm(b, a % b);
 }
-
-/*Method 2: Easy to evaluate*/
-export default function euclideanAlgorithm2(originalA, originalB) {
-  const a = Math.abs(originalA);
-  const b = Math.abs(originalB);
-  
-  while(a != b){
-    [a,b] = a>b : [a-b, b] : [a, b-a]
-  }
-  
-  return a || b;
-}
diff --git a/src/algorithms/math/euclidean-algorithm/euclideanAlgorithmIterative.js b/src/algorithms/math/euclidean-algorithm/euclideanAlgorithmIterative.js
@@ -0,0 +1,20 @@
+/**
+ * Iterative version of Euclidean Algorithm of finding greatest common divisor (GCD).
+ * @param {number} originalA
+ * @param {number} originalB
+ * @return {number}
+ */
+export default function euclideanAlgorithmIterative(originalA, originalB) {
+  // Make input numbers positive.
+  let a = Math.abs(originalA);
+  let b = Math.abs(originalB);
+
+  // Subtract one number from another until both numbers would become the same.
+  // This will be out GCD. Also quit the loop if one of the numbers is zero.
+  while (a && b && a !== b) {
+    [a, b] = a > b ? [a - b, b] : [a, b - a];
+  }
+
+  // Return the number that is not equal to zero since the last subtraction (it will be a GCD).
+  return a || b;
+}
