py/modmath: Tighten math.gcd recursion.

jbbjarnason · jbbjarnason · commit 5dba62d2f32b · 2022-02-22T16:56:03.000Z
Refactor math.gcd algorithm to recursive Euclid algorithm, see more info here: https://www.rosettacode.org/wiki/Greatest_common_divisor#C.
diff --git a/py/modmath.c b/py/modmath.c
@@ -202,29 +202,17 @@ MATH_FUN_1(lgamma, lgamma)
 
 // gcd(x, y): return the greatest common divisor
 STATIC mp_int_t gcd_func(mp_int_t x, mp_int_t y) {
-    if (x == 0) {
-        return y;
-    }
-    if (y == 0) {
-        return x;
-    }
-    if (x == y) {
-        return x;
-    }
-    if (x > y) {
-        return gcd_func(x - y, y);
-    }
-    return gcd_func(x, y - x);
+    return (y != 0) ? gcd_func(y, x % y) : x;
 }
 STATIC mp_obj_t mp_math_gcd(size_t n_args, const mp_obj_t *args) {
     mp_int_t e = mp_obj_get_int(args[--n_args]);
     mp_int_t d = mp_obj_get_int(args[--n_args]);
     // calc absolute value manually, makes it unnecessary to include stdlib
     if (d < 0) {
-        d *= -1;
+        d = -d;
     }
     if (e < 0) {
-        e *= -1;
+        e = -e;
     }
 
     mp_int_t ans = gcd_func(d, e);
@@ -236,7 +224,7 @@ STATIC mp_obj_t mp_math_gcd(size_t n_args, const mp_obj_t *args) {
     do {
         mp_int_t next_variable = mp_obj_get_int(args[--n_args]);
         if (next_variable < 0) {
-            next_variable *= -1;
+            next_variable = -next_variable;
         }
         ans = gcd_func(next_variable, ans);
     } while (n_args > 0);
diff --git a/tests/float/math_fun_special.py b/tests/float/math_fun_special.py
@@ -65,6 +65,8 @@
             (-9, -2),
             (0, 0),
             (6, 30, 40, -60, 20, 40),
+            (2147483643, 42),
+            (-9223372036854775807, -922337203685477580, -92233720368547758)
         ),
     ),
 ]

Original file line number	Diff line number	Diff line change
`@@ -65,6 +65,8 @@`
`65`	`65`	`(-9, -2),`
`66`	`66`	`(0, 0),`
`67`	`67`	`(6, 30, 40, -60, 20, 40),`
	`68`	`+ (2147483643, 42),`
	`69`	`+ (-9223372036854775807, -922337203685477580, -92233720368547758)`
`68`	`70`	`),`
`69`	`71`	`),`
`70`	`72`	`]`