[issue22486] Add math.gcd()

[Stefan Behnel]

Stefan Behnel added the comment:

Patch 7 works for me. Why are the two Py_ABS() calls at the end needed when we start off the algorithm with long_abs()?

The Lehmer code is complex (I guess that's why you added the pure Euclidean implementation), but it's the right algorithm to use here, so I'd say we should. It's 4% faster than the Euclidean code for the fractions benchmark when using 30 bit digits, but (surprisingly enough) about the same speed with 15 bit digits. There is no major difference to expect here as the numbers are perpetually normalised in Fractions and thus kept small (usually small enough to fit into a 64bit integer), i.e. Euclid should do quite well on them.

The difference for big numbers is substantial though:

Euclid:

$ ./python -m timeit -s 'from math import gcd; a = 2**123 + 3**653 + 5**23 + 7**49; b = 2**653 + 2**123 + 5**23 + 11**34' 'gcd(a,b)'
10000 loops, best of 3: 71 usec per loop

Lehmer:

$ ./python -m timeit -s 'from math import gcd; a = 2**123 + 3**653 + 5**23 + 7**49; b = 2**653 + 2**123 + 5**23 + 11**34' 'gcd(a,b)'
100000 loops, best of 3: 11.6 usec per loop

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue22486>
_______________________________________