Added Euclidean Algorithm to the number theory section

jonathanxia · jonathanxia · commit 6e368859f8a8 · 2016-05-31T21:22:19.000-07:00
Added the code, data, and description for the euclidean algorithm in the
number theory section.
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -15,7 +15,8 @@
   "number_theory": {
     "name": "Number Theory",
     "list": {
-      "seive_of_erathrones": "Seive of Erathrones"
+      "seive_of_erathrones": "Seive of Erathrones",
+	  "euclidean_algorithm": "Euclidean Algorithm"
     }
   },
   "cryptography": {
diff --git a/algorithm/number_theory/euclidean_algorithm/basic/code.js b/algorithm/number_theory/euclidean_algorithm/basic/code.js
@@ -0,0 +1,28 @@
+logger._print("Finding the greatest common divisor of " + a[0] + " and " + a[1]);
+
+logger._print("Checking if first number is at most the second number");
+
+if(a[0] > a[1]) {
+    var tmp = a[0];
+    a[0] = a[1];
+    a[1] = tmp;
+    logger._print("The first number is bigger than the second number. Switching the numbers.");
+    tracer._setData(a)._wait();
+}
+
+while(a[0] > 0) {
+    logger._print(a[1] + " % " + a[0] + " = " + a[1]%a[0]);
+    logger._print("Switching a[1] with a[1]%a[0]");
+    a[1] %= a[0];
+    tracer._notify(1, a[1])._wait();
+    logger._print("Now switching the two values to keep a[0] < a[1]");
+    var tmp = a[0];
+    a[0] = a[1];
+    a[1] = tmp;
+    tracer._notify(0, a[0]);
+    tracer._notify(1, a[1])._wait();
+    tracer._denotify(0);
+    tracer._denotify(1);
+}
+
+logger._print("The greatest common divisor is " + a[1]);
diff --git a/algorithm/number_theory/euclidean_algorithm/basic/data.js b/algorithm/number_theory/euclidean_algorithm/basic/data.js
@@ -0,0 +1,6 @@
+var tracer = new Array1DTracer('Euclidean Algorithm');
+var a = [];
+a.push(465);
+a.push(255)
+tracer._setData(a);
+var logger = new LogTracer();
diff --git a/algorithm/number_theory/euclidean_algorithm/desc.json b/algorithm/number_theory/euclidean_algorithm/desc.json
@@ -0,0 +1,13 @@
+{
+  "Euclidean Algorithm": "Finds the greatest common divisor of two positive integers. The Euclidean Algorithm uses the fact that gcd(m, n) = gcd(m, n % m).",
+  "Complexity": {
+    "time": "O(log(m)log(n))",
+    "space": "O(1)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Euclidean_algorithm'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Euclidean Algorithm"
+  }
+}
