This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author scoder
Recipients scoder
Date 2014-09-24.20:40:35
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
fractions.gcd() is required for normalising numerator and denominator of the Fraction data type. Some speed improvements were applied to Fraction in issue 22464, now the gcd() function takes up about half of the instantiation time in the benchmark in issue 22458, which makes it quite a heavy part of the overall Fraction computation time.

The current implementation is

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

Reimplementing it in C would provide for much faster calculations. Here is a Cython version that simply drops the calculation loop into C as soon as the numbers are small enough to fit into a C long long int:

def _gcd(a, b):
    # Try doing all computation in C space.  If the numbers are too large
    # at the beginning, retry until they are small enough.
    cdef long long ai, bi
    while b:
            ai, bi = a, b
        except OverflowError:
            # switch to C loop
            while bi:
                ai, bi = bi, ai%bi
            return ai
        a, b = b, a%b
    return a

It's substantially faster already because the values will either be small enough right from the start or quickly become so after a few iterations with Python objects.

Further improvements should be possible with a dedicated PyLong implementation based on Lehmer's GCD algorithm:
Date User Action Args
2014-09-24 20:40:35scodersetrecipients: + scoder
2014-09-24 20:40:35scodersetmessageid: <>
2014-09-24 20:40:35scoderlinkissue22486 messages
2014-09-24 20:40:35scodercreate