gh-102221: speed up math.lcm by swapping numbers

kevin1kevin1k · kevin1kevin1k · commit e35ba2a74007 · 2025-06-15T14:17:17.000+08:00
diff --git a/Misc/NEWS.d/next/Library/2023-10-29-15-35-57.gh-issue-102221.fQnOaT.rst b/Misc/NEWS.d/next/Library/2023-10-29-15-35-57.gh-issue-102221.fQnOaT.rst
@@ -0,0 +1 @@
+Speed up math lcm
diff --git a/Modules/mathmodule.c b/Modules/mathmodule.c
@@ -769,7 +769,15 @@ long_lcm(PyObject *a, PyObject *b)
     if (_PyLong_IsZero((PyLongObject *)a) || _PyLong_IsZero((PyLongObject *)b)) {
         return PyLong_FromLong(0);
     }
-    g = _PyLong_GCD(a, b);
+
+    /* Make sure a <= b to speed up (a // g) * b; see #102221 for details. */
+    if (_PyLong_DigitCount((PyLongObject *)b) < _PyLong_DigitCount((PyLongObject *)a)) {
+        g = a;
+        a = b;
+        b = g;
+    }
+
+    g = _PyLong_GCD(b, a);
     if (g == NULL) {
         return NULL;
     }
@@ -830,7 +838,7 @@ math_lcm_impl(PyObject *module, PyObject * const *args,
             Py_DECREF(x);
             continue;
         }
-        Py_SETREF(res, long_lcm(res, x));
+        Py_SETREF(res, long_lcm(x, res));
         Py_DECREF(x);
         if (res == NULL) {
             return NULL;
