Stefan Behnel added the comment: 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. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue22464> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com