C API: Consider adding a public PyLong_GCD() function

@scoder

Feature or enhancement

The private _PyLong_GCD() function was removed in Python 3.13: see PR #108429.

@scoder asked what is the intended replacement for _PyLong_GCD(). I suppose that the replacement is to call math.gcd().

Is it worth it to add a public PyLong_GCD() function to the C API? Is it commonly used?

A code search for _PyLong_GCD is PyPI top 5,000 projects found 0 projects using it.

@scoder: What is your use case for _PyLong_GCD()? Using math.gcd() doesn't solve your use case?

Linked PRs

gh-111139: Optimize math.gcd(int, int) #113887

@serhiy-storchaka

cc @serhiy-storchaka @mdickinson

I use the function in quicktions, a fast reimplementation of the fractions.Fraction data type.

Like the original, it depends heavily on the GCD performance. I tried calling math.gcd() instead and it's over 7% slower in the telco benchmark on Python 3.10/3.11.

If there is no reason for this specific function to be removed from the API, I'll simply ask to have it back. It's there, it's unlikely to change, so there is no reason not to expose it.

If direct call of _PyLong_GCD() makes the code 7% faster than using math.gcd(), it is perhaps not worth. Note that many methods of builtin types (like str.upper()) are not exposed in the C API. General Python object or method call API is the way to use them.

If direct call of _PyLong_GCD() makes the code 7% faster than using math.gcd(), it is perhaps not worth.

If no public function will be added, then please put the old function back in. There was no reason to remove it and break existing code.

The rationale for the removal was given in the issue.

The rationale for the removal was given in the issue.

No, it really wasn't. But I was able to reverse engineer some reasoning based on hints that you gave in discussions that were linked in random comments spread across the huge ticket. I'm perfectly fine with removing "private" and "private by convention" APIs when they get in the way or when they cannot easily be kept alive. But that was not part of the reasoning.

I do not understand why existing code must be broken without need. And there is really no reason at all why this specific function cannot be public. It's literally just a single line in longobject.h that didn't hurt anyone for the last eight years, and that would happily continue to not get in the way if it hadn't been removed. Now it does get in the way, simply by no longer being there.

If direct call of _PyLong_GCD() makes the code 7% faster than using math.gcd(), it is perhaps not worth.

quicktions is all about being fast. That's the whole point of using it instead of fractions.Fraction. Honestly, for 7% more performance in an application benchmark, I'd consider ripping the GCD implementation in CPython out and copying it over. But that would involve a huge tail of code dependencies because it's tightly linked into longobject.c and the PyLong internals. It would be much easier if CPython simply exposed the function – as it did until a week ago, when 3.13a1 was released.

I created PR #111162

gh-106320: Re-add some PyLong/PyDict C-API functions (GH-#111162)

The _PyLong_GCD() function was restored by commit a8a89fc.

pythongh-111139: Optimize math.gcd(int, int)

Like the original, it depends heavily on the GCD performance. I tried calling math.gcd() instead and it's over 7% slower in the telco benchmark on Python 3.10/3.11.

I wrote PR gh-113887 which makes math.gcd() 7% faster on the most common case: math.gcd(int, int) (2 arguments which are exactly of the type int).

gh-111139: Optimize math.gcd(int, int) (#113887)

@scoder

I wrote PR #113887 which makes math.gcd() 7% faster on the most common case: math.gcd(int, int)

@scoder: With this PR being merged, I don't think that it's still relevant to add PyLong_GCD() to the public C API. What do you think?

pythongh-111139: Optimize math.gcd(int, int) (python#113887)

pythongh-106320: Re-add some PyLong/PyDict C-API functions (GH-python…

pythongh-111139: Optimize math.gcd(int, int) (python#113887)

@da-woods

@da-woods: Hi, do you have an opinion on this issue? Can Cython be satisfied by faster math.gcd(x, y) in Python 3.13? Or do you still consider that _PyLong_GCD() is way faster? You can play with Python 3.13 alpha3 release which includes my optimization (93930ea).

@scoder

I don't have an opinion - Cython doesn't use it directly.

Based on the discussion above, I think @scoder's interest is from https://github.com/scoder/quicktions which I'm not involved in.

@scoder

I close the issue. IMO it's not worth it to expose _PyLong_GCD(), sorry.

Calling math.gcd() is 1.05x slower than calling directly _PyLong_GCD(): 5 ms slower (compared to 91.1 ms).

Mean +- std dev: [_PyLong_GCD] 91.1 ms +- 1.0 ms -> [math_gcd] 96.1 ms +- 0.5 ms: 1.05x slower

IMO this slowdown is acceptable and it's not worth it to add a specialized _PyLong_GCD(), since the quicktions project is the only one known to need this private function.

I suggest quicktions to write even more efficient code:

Specialize its gcd() function to handle the most common case where two Python int object are "small integers" and implement GCD itself.
Fallback on math.gcd() for larger numbers.

IMO "inlining" _PyLong_GCD() fast-path directly in quicktions should make the code even faster.

On Python 3.13, you can use:

if (_PyLong_IsCompact(x) && _PyLong_IsCompact(y)) {
    Py_ssize_t a = _PyLong_CompactValue(x);
    Py_ssize_t b = _PyLong_CompactValue(y);
    return ...;
}

Sadly, that's yet another private API :-(

I don't have an opinion - Cython doesn't use it directly.

Oh sorry, I thought that it was Cython which used it directly.

Based on the discussion above, I think @scoder's interest is from https://github.com/scoder/quicktions which I'm not involved in.

I hacked Cython to make it work on Python 3.13a4: cython/cython#6003

I had to hack quicktions to make it work with Cython 3 on Python 3:

diff --git a/src/quicktions.pyx b/src/quicktions.pyx
index 2df9560..5e9480f 100644
--- a/src/quicktions.pyx
+++ b/src/quicktions.pyx
@@ -366,7 +366,7 @@ cdef class Fraction:
 
         cdef bint _normalize = True
         if denominator is None:
-            if type(numerator) is int or type(numerator) is long:
+            if type(numerator) is int or type(numerator) is int:
                 self._numerator = numerator
                 self._denominator = 1
                 return
@@ -422,7 +422,7 @@ cdef class Fraction:
         elif type(numerator) is int is type(denominator):
             pass  # *very* normal case
 
-        elif PY_MAJOR_VERSION < 3 and type(numerator) is long is type(denominator):
+        elif PY_MAJOR_VERSION < 3 and type(numerator) is int is type(denominator):
             pass  # *very* normal case
 
         elif type(numerator) is Fraction is type(denominator):
@@ -861,7 +861,7 @@ cdef class Fraction:
         if x is not None:
             return NotImplemented
 
-        if isinstance(b, (int, long)):
+        if isinstance(b, int):
             return _pow(a.numerator, a.denominator, b, 1)
         elif isinstance(b, (Fraction, Rational)):
             return _pow(a.numerator, a.denominator, b.numerator, b.denominator)
@@ -883,7 +883,7 @@ cdef class Fraction:
             # If a is an int, keep it that way if possible.
             return a ** bn
 
-        if isinstance(a, (int, long)):
+        if isinstance(a, int):
             return _pow(a, 1, bn, bd)
         if isinstance(a, (Fraction, Rational)):
             return _pow(a.numerator, a.denominator, bn, bd)
@@ -1081,7 +1081,7 @@ cdef class Fraction:
 
     @cython.final
     cdef _eq(a, b):
-        if type(b) is int or type(b) is long:
+        if type(b) is int or type(b) is int:
             return a._numerator == b and a._denominator == 1
         if type(b) is Fraction:
             return (a._numerator == (<Fraction>b)._numerator and
@@ -1112,7 +1112,7 @@ cdef class Fraction:
 
         """
         # convert other to a Rational instance where reasonable.
-        if isinstance(other, (int, long)):
+        if isinstance(other, int):
             a = self._numerator
             b = self._denominator * other
         elif type(other) is Fraction:
@@ -1444,7 +1444,7 @@ cdef forward(a, b, math_func monomorphic_operator, pyoperator):
     an, ad = (<Fraction>a)._numerator, (<Fraction>a)._denominator
     if type(b) is Fraction:
         return monomorphic_operator(an, ad, (<Fraction>b)._numerator, (<Fraction>b)._denominator)
-    elif isinstance(b, (int, long)):
+    elif isinstance(b, int):
         return monomorphic_operator(an, ad, b, 1)
     elif isinstance(b, (Fraction, Rational)):
         return monomorphic_operator(an, ad, b.numerator, b.denominator)
@@ -1458,7 +1458,7 @@ cdef forward(a, b, math_func monomorphic_operator, pyoperator):
 
 cdef reverse(a, b, math_func monomorphic_operator, pyoperator):
     bn, bd = (<Fraction>b)._numerator, (<Fraction>b)._denominator
-    if isinstance(a, (int, long)):
+    if isinstance(a, int):
         return monomorphic_operator(a, 1, bn, bd)
     elif isinstance(a, Rational):
         return monomorphic_operator(a.numerator, a.denominator, bn, bd)
@@ -1536,16 +1536,10 @@ cdef extern from *:
             *length = PyBytes_GET_SIZE(string);
             *data   = PyBytes_AS_STRING(string);
         } else {
-        #if CYTHON_PEP393_ENABLED
             if (PyUnicode_READY(string) < 0) return -1;
             *kind   = PyUnicode_KIND(string);
             *length = PyUnicode_GET_LENGTH(string);
             *data   = PyUnicode_DATA(string);
-        #else
-            *kind   = 0;
-            *length = PyUnicode_GET_SIZE(string);
-            *data   = (void*)PyUnicode_AS_UNICODE(string);
-        #endif
         }
         return 0;
     }

I patched the benchmark to use pyperf to get more reliable numbers:

diff --git a/benchmark/telco_fractions.py b/benchmark/telco_fractions.py
index a27d4b5..a7007af 100644
--- a/benchmark/telco_fractions.py
+++ b/benchmark/telco_fractions.py
@@ -110,7 +110,7 @@ def main(n, cls=Fraction):
     return times
 
 
-if __name__ == "__main__":
+def bench():
     import optparse
     parser = optparse.OptionParser(
         usage="%prog [options]",
@@ -137,3 +137,11 @@ if __name__ == "__main__":
     results.sort()
     print('%.4f  (mean)' % (fsum(results[1:-1]) / (len(results) - 2)))
     print('%.4f  (median)' % (results[len(results) // 2]))
+
+def bench():
+    import pyperf
+    runner = pyperf.Runner()
+    runner.bench_func('fraction', run, Fraction)
+
+if __name__ == "__main__":
+    bench()

I installed Cython and then quicktions in a venv.

At the end, I get these numbers, comparison between _PyLong_GCD() and math.gcd():

$ python -m pyperf compare_to _PyLong_GCD.json math_gcd.json 
Mean +- std dev: [_PyLong_GCD] 91.1 ms +- 1.0 ms -> [math_gcd] 96.1 ms +- 0.5 ms: 1.05x slower

math.gcd() adds more checks and indirections:

if (unlikely(PyMethod_Check(__pyx_t_3))) {
__Pyx_PyObject_FastCall()
if (nargs == 0 && kwargs == NULL)
if (nargs == 1 && kwargs == NULL)
if (kwargs == NULL)
PyVectorcall_Function()
cfunction_vectorcall_FASTCALL()
if (cfunction_check_kwargs(tstate, func, kwnames))
cfunction_enter_call()
PyCFunction_GET_SELF(func)
_Py_LeaveRecursiveCallTstate(tstate)

Hum. I think that it's hard to avoid these additional checks and indirections, compare to calling directly _PyLong_GCD(). This code is already optimized.

gh-106320: Re-add _PyLong_FromByteArray(), _PyLong_AsByteArray() and …

pythongh-106320: Re-add some PyLong/PyDict C-API functions (GH-python…

pythongh-111139: Optimize math.gcd(int, int) (python#113887)

(Split off discussion from #141049.)

IMO this slowdown is acceptable and it's not worth it to add a specialized _PyLong_GCD()

Sorry, I don't understand well this decision: "Honestly, for 7% more performance in an application benchmark, I'd consider ripping the GCD implementation in CPython out and copying it over. " (c)

What's a price on the CPython side? This not something fancy, it's a mathematical function with a clear interface, that will be stable for centuries.

Navigation Menu

Repository navigation

C API: Consider adding a public PyLong_GCD() function #111139

Feature or enhancement

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

C API: Consider adding a public PyLong_GCD() function #111139

Description

Feature or enhancement

Linked PRs

Activity

vstinner commented on Oct 20, 2023

scoder commented on Oct 21, 2023

serhiy-storchaka commented on Oct 21, 2023

scoder commented on Oct 21, 2023

vstinner commented on Oct 21, 2023

scoder commented on Oct 21, 2023

scoder commented on Oct 21, 2023

vstinner commented on Nov 15, 2023

vstinner commented on Jan 10, 2024

vstinner commented on Jan 10, 2024

vstinner commented on Feb 15, 2024

da-woods commented on Feb 15, 2024

vstinner commented on Feb 16, 2024

skirpichev commented on Nov 6, 2025

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions