[pypy-issue] Issue #3031: math.gcd much slower than CPython (pypy/pypy)

[Luanna]

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.