Fix gcd (keon#760)

lazarko · web-flow · commit 3074384b6402 · 2021-03-07T08:40:28.000+09:00
* fix: add input argument checks and lcm/gcd can handle negative numbers

* test: add new tests for gcd/lcm to test new fixes
diff --git a/algorithms/maths/gcd.py b/algorithms/maths/gcd.py
@@ -1,15 +1,27 @@
 def gcd(a, b):
     """Computes the greatest common divisor of integers a and b using
     Euclid's Algorithm.
+    gcd{𝑎,𝑏}=gcd{−𝑎,𝑏}=gcd{𝑎,−𝑏}=gcd{−𝑎,−𝑏}
+    See proof: https://proofwiki.org/wiki/GCD_for_Negative_Integers
     """
+    a_int = isinstance(a, int)
+    b_int = isinstance(b, int)
+    a = abs(a)
+    b = abs(b)
+    if not(a_int or b_int):
+        raise ValueError("Input arguments are not integers")
+
+    if (a == 0) or (b == 0) :
+        raise ValueError("One or more input arguments equals zero")
+
     while b != 0:
         a, b = b, a % b
     return a
 
 
 def lcm(a, b):
     """Computes the lowest common multiple of integers a and b."""
-    return a * b / gcd(a, b)
+    return abs(a) * abs(b) / gcd(a, b)
 
 
 """
diff --git a/tests/test_maths.py b/tests/test_maths.py
@@ -29,6 +29,7 @@
 )
 
 import unittest
+import pytest
 
 
 class TestPower(unittest.TestCase):
@@ -128,8 +129,37 @@ def test_gcd(self):
         self.assertEqual(4, gcd(8, 12))
         self.assertEqual(1, gcd(13, 17))
 
+    def test_gcd_non_integer_input(self):
+        with pytest.raises(ValueError, match=r"Input arguments are not integers"):
+            gcd(1.0, 5)
+            gcd(5, 6.7)
+            gcd(33.8649, 6.12312312)
+
+    def test_gcd_zero_input(self):
+        with pytest.raises(ValueError, match=r"One or more input arguments equals zero"):
+            gcd(0, 12)
+            gcd(12, 0)
+            gcd(0, 0)
+
+    def test_gcd_negative_input(self):
+        self.assertEqual(1, gcd(-13, -17))
+        self.assertEqual(4, gcd(-8, 12))
+        self.assertEqual(8, gcd(24, -16))
+
     def test_lcm(self):
         self.assertEqual(24, lcm(8, 12))
+        self.assertEqual(5767, lcm(73, 79))
+
+    def test_lcm_negative_numbers(self):
+        self.assertEqual(24, lcm(-8, -12))
+        self.assertEqual(5767, lcm(73, -79))
+        self.assertEqual(1, lcm(-1, 1))
+
+    def test_lcm_zero_input(self):
+        with pytest.raises(ValueError, match=r"One or more input arguments equals zero"):
+            lcm(0, 12)
+            lcm(12, 0)
+            lcm(0, 0)
 
     def test_trailing_zero(self):
         self.assertEqual(1, trailing_zero(34))
@@ -140,6 +170,7 @@ def test_gcd_bit(self):
         self.assertEqual(1, gcd(13, 17))
 
 
+
 class TestGenerateStroboGrammatic(unittest.TestCase):
     """[summary]
     Test for the file generate_strobogrammatic.py
