New issue 3031: math.gcd much slower than CPython https://bitbucket.org/pypy/pypy/issues/3031/mathgcd-much-slower-than-cpython
Luanna: 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. _______________________________________________ pypy-issue mailing list pypy-issue@python.org https://mail.python.org/mailman/listinfo/pypy-issue
