Merge pull request nryoung#29 from utsavgupta/master

nryoung · nryoung · commit 33300dd514de · 2012-11-18T13:41:14.000-08:00
Added Extended Greatest Common Divisor Algorithm
diff --git a/algorithms/math/__init__.py b/algorithms/math/__init__.py
diff --git a/algorithms/math/extended_gcd.py b/algorithms/math/extended_gcd.py
@@ -0,0 +1,41 @@
+"""
+    extended_gcd.py
+
+    This module implements the extended greatest common divider algorithm.
+
+    Pre: two integers a and b
+    Post: a tuple (x, y) where a*x + b*y = gcd(a, b)
+
+    Pseudo Code: http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
+"""
+
+
+def extended_gcd(p, q):
+
+    (a, b) = (p, q)
+
+    if a < 0:
+        a = -1 * a
+
+    if b < 0:
+        b = -1 * b
+
+    x0 = 0
+    y1 = 0
+
+    x1 = 1
+    y0 = 1
+
+    while(b != 0):
+        quotient = a / b
+        (a, b) = (b, a % b)
+        (x1, x0) = (x0 - quotient * x1, x1)
+        (y1, y0) = (y0 - quotient * y1, y1)
+
+    if p < 0:
+        y0 = -1 * y0
+
+    if q < 0:
+        x0 = -1 * x0
+
+    return (y0, x0)
diff --git a/algorithms/tests/test_math.py b/algorithms/tests/test_math.py
@@ -0,0 +1,26 @@
+import unittest
+from ..math.extended_gcd import extended_gcd
+
+
+class TestExtendedGCD(unittest.TestCase):
+
+    def test_extended_gcd(self):
+        # Find extended_gcd of 35 and 77
+        (a, b) = extended_gcd(35, 77)
+        self.assertIs(35 * a + 77 * b, 7)
+
+        # Find extended_gcd of 15 and 19
+        (a, b) = extended_gcd(15, 19)
+        self.assertIs(15 * a + 19 * b, 1)
+
+        # Find extended_gcd of 18 and 9
+        (a, b) = extended_gcd(18, 9)
+        self.assertIs(18 * a + 9 * b, 9)
+
+        # Find extended_gcd of 99 and 81
+        (a, b) = extended_gcd(99, 81)
+        self.assertIs(99 * a + 81 * b, 9)
+
+        # Find extended_gcd of 50 and 15
+        (a, b) = extended_gcd(50, 15)
+        self.assertIs(50 * a + 15 * b, 5)
