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 mark.dickinson, rhettinger, scoder, serhiy.storchaka
Date 2014-09-23.22:09:12
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
This simple Cython variant of gcd() is substantially faster for me (you may consider it pseudo-code for a C implementation):

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 tries to drop the two numbers into C long-long-ints as soon as possible, and only runs the calculation in Python space until they are small enough to fit. In most cases, this will be either right from the start or fairly quickly after only a few iterations.
Date User Action Args
2014-09-23 22:09:12scodersetrecipients: + scoder, rhettinger, mark.dickinson, serhiy.storchaka
2014-09-23 22:09:12scodersetmessageid: <>
2014-09-23 22:09:12scoderlinkissue22464 messages
2014-09-23 22:09:12scodercreate