Author: Carl Friedrich Bolz-Tereick <[email protected]>
Branch: py3.6
Changeset: r96959:aa95fe7b71b4
Date: 2019-07-10 13:46 +0200
http://bitbucket.org/pypy/pypy/changeset/aa95fe7b71b4/
Log: (Luanna): integrate new gcd algorithm into the pypy math module
diff --git a/pypy/module/math/__init__.py b/pypy/module/math/__init__.py
--- a/pypy/module/math/__init__.py
+++ b/pypy/module/math/__init__.py
@@ -5,7 +5,6 @@
class Module(MixedModule):
appleveldefs = {
'factorial' : 'app_math.factorial',
- 'gcd' : 'app_math.gcd',
}
interpleveldefs = {
@@ -57,5 +56,6 @@
'gamma' : 'interp_math.gamma',
'lgamma' : 'interp_math.lgamma',
'isclose' : 'interp_math.isclose',
+ 'gcd' : 'interp_math.gcd',
}
diff --git a/pypy/module/math/app_math.py b/pypy/module/math/app_math.py
--- a/pypy/module/math/app_math.py
+++ b/pypy/module/math/app_math.py
@@ -47,10 +47,3 @@
res, _, shift = _fac1(x)
return res << shift
-def gcd(x, y):
- """greatest common divisor of x and y"""
- x = abs(index(x))
- y = abs(index(y))
- while x > 0:
- x, y = y % x, x
- return y
diff --git a/pypy/module/math/interp_math.py b/pypy/module/math/interp_math.py
--- a/pypy/module/math/interp_math.py
+++ b/pypy/module/math/interp_math.py
@@ -484,3 +484,23 @@
diff <= math.fabs(rel_tol * a)) or
diff <= abs_tol)
return space.newbool(result)
+
+
+def gcd(space, w_a, w_b):
+ """greatest common divisor of a and b"""
+ from rpython.rlib import rbigint
+ w_a = space.abs(space.index(w_a))
+ w_b = space.abs(space.index(w_b))
+ try:
+ a = space.int_w(w_a)
+ b = space.int_w(w_b)
+ g = rbigint.gcd_binary(a, b)
+ return space.newint(g)
+ except OperationError as e:
+ if not e.match(space, space.w_OverflowError):
+ raise
+
+ a = space.bigint_w(w_a)
+ b = space.bigint_w(w_b)
+ g = a.gcd(b)
+ return space.newlong_from_rbigint(g)
diff --git a/pypy/module/math/test/test_math.py
b/pypy/module/math/test/test_math.py
--- a/pypy/module/math/test/test_math.py
+++ b/pypy/module/math/test/test_math.py
@@ -371,6 +371,8 @@
assert math.gcd(0, -10) == 10
assert math.gcd(0, 0) == 0
raises(TypeError, math.gcd, 0, 0.0)
+ assert math.gcd(-3**10*5**20*11**8, 2**5*3**5*7**20) == 3**5
+ assert math.gcd(64, 200) == 8
def test_inf_nan(self):
import math
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
