[pypy-issue] Issue #3031: math.gcd much slower than CPython (pypy/pypy)
issues-reply at bitbucket.org
Thu Jun 27 09:55:31 EDT 2019
New issue 3031: math.gcd much slower than CPython
CPython uses Lehmer's GCD algorithm which is about ten times faster for sufficiently large values. A test that shows this:
from fractions import Fraction
sum(Fraction(1, n) for n in range(1, 10**4))
It takes 70 seconds in PyPy3 but only 3 seconds in CPython.
The good news is that Lehmer’s algorithm is easy to implement. CPython’s implementation is in [longobject.c](https://golang.org/src/math/big/int.go). There’s also an easier to read implementation [in Go](https://golang.org/src/math/big/int.go). For efficiency Lehmer’s algorithm needs to operate on machine words, so the implementation needs to be at the RPython level which I’m unfamiliar with. I can provide an app-level implementation if that is useful although it is only faster for very large values.
Please let me know if there’s any way I could help.
More information about the pypy-issue