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 <1411510152.62.0.28596088578.issue22464@psf.upfronthosting.co.za>
In-reply-to
Content
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:
        try:
            ai, bi = a, b
        except OverflowError:
            pass
        else:
            # 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.
History
Date User Action Args
2014-09-23 22:09:12scodersetrecipients: + scoder, rhettinger, mark.dickinson, serhiy.storchaka
2014-09-23 22:09:12scodersetmessageid: <1411510152.62.0.28596088578.issue22464@psf.upfronthosting.co.za>
2014-09-23 22:09:12scoderlinkissue22464 messages
2014-09-23 22:09:12scodercreate