[pypy-commit] pypy py3.6: (Luanna): integrate new gcd algorithm into the pypy math module
Author: Carl Friedrich Bolz-Tereick
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
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy py3.6: no need to call abs twice
Author: Carl Friedrich Bolz-Tereick Branch: py3.6 Changeset: r96960:de29534e71f5 Date: 2019-07-10 15:11 +0200 http://bitbucket.org/pypy/pypy/changeset/de29534e71f5/ Log:no need to call abs twice 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 @@ -489,8 +489,8 @@ 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)) +w_a = space.index(w_a) +w_b = space.index(w_b) try: a = space.int_w(w_a) b = space.int_w(w_b) ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy default: (Luanna, cfbolz): add rbigint.gcd to compute the greatest common divisor of two
Author: Carl Friedrich Bolz-Tereick Branch: Changeset: r96957:bf3310921e45 Date: 2019-07-10 13:38 +0200 http://bitbucket.org/pypy/pypy/changeset/bf3310921e45/ Log:(Luanna, cfbolz): add rbigint.gcd to compute the greatest common divisor of two rbigint instances using Lehmer's algorithm: https://bitbucket.org/pypy/pypy/issues/3031/mathgcd-much-slower- than-cpython https://en.wikipedia.org/wiki/Lehmer's_GCD_algorithm diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -1423,6 +1423,12 @@ bits = ovfcheck((i-1) * SHIFT) + msd_bits return bits +def gcd(self, other): +""" Compute the (always positive) greatest common divisor of self and +other """ +return gcd_lehmer(self.abs(), other.abs()) + + def __repr__(self): return "" % (self._digits, self.sign, self.numdigits(), len(self._digits), @@ -2960,3 +2966,88 @@ z.setdigit(pdigit, accum) z._normalize() return z + + +def gcd_binary(a, b): +if a == 0: +return b + +if b == 0: +return a + +a, b = abs(a), abs(b) + +shift = 0 +while (a | b) & 1 == 0: +a >>= 1 +b >>= 1 +shift += 1 + +while a & 1 == 0: +a >>= 1 + +while b & 1 == 0: +b >>= 1 + +while a != b: +a, b = abs(a - b), min(a, b) +while a & 1 == 0: +a >>= 1 + +return a << shift + +def lehmer_xgcd(a, b): +s_old, s_new = 1, 0 +t_old, t_new = 0, 1 +while b >> (SHIFT >> 1): +q, r = a // b, a % b + +a, b = b, r +s_old, s_new = s_new, s_old - q * s_new +t_old, t_new = t_new, t_old - q * t_new + +return s_old, t_old, s_new, t_new + +def gcd_lehmer(a, b): +if a.lt(b): +a, b = b, a + +while b.size > 1: +a_ms = a.digit(a.size-1) + +x = 0 +while a_ms & (0xFF << SHIFT-8) == 0: +a_ms <<= 8 +x += 8 + +while a_ms & (1 << SHIFT-1) == 0: +a_ms <<= 1 +x += 1 + +a_ms |= a.digit(a.size-2) >> SHIFT-x + +if a.size == b.size: +b_ms = (b.digit(b.size-1) << x) | (b.digit(b.size-2) >> SHIFT-x) +elif a.size == b.size+1: +b_ms = b.digit(b.size-1) >> SHIFT-x +else: +b_ms = 0 + +if b_ms >> (SHIFT+1 >> 1) == 0: +a, b = b, a.mod(b) +continue + +s_old, t_old, s_new, t_new = lehmer_xgcd(a_ms, b_ms) + +n_a = a.int_mul(s_new).add(b.int_mul(t_new)).abs() +b = a.int_mul(s_old).add(b.int_mul(t_old)).abs() +a = n_a + +if a.lt(b): +a, b = b, a + +if not b.tobool(): +return a + +a = a.mod(b) +return rbigint.fromint(gcd_binary(b.toint(), a.toint())) diff --git a/rpython/rlib/test/test_rbigint.py b/rpython/rlib/test/test_rbigint.py --- a/rpython/rlib/test/test_rbigint.py +++ b/rpython/rlib/test/test_rbigint.py @@ -11,12 +11,13 @@ from rpython.rlib import rbigint as lobj from rpython.rlib.rarithmetic import r_uint, r_longlong, r_ulonglong, intmask from rpython.rlib.rbigint import (rbigint, SHIFT, MASK, KARATSUBA_CUTOFF, -_store_digit, _mask_digit, InvalidEndiannessError, InvalidSignednessError) +_store_digit, _mask_digit, InvalidEndiannessError, InvalidSignednessError, +gcd_lehmer, lehmer_xgcd, gcd_binary) from rpython.rlib.rfloat import NAN from rpython.rtyper.test.test_llinterp import interpret from rpython.translator.c.test.test_standalone import StandaloneTests -from hypothesis import given, strategies, example +from hypothesis import given, strategies, example, settings longs = strategies.builds( long, strategies.integers()) @@ -836,6 +837,27 @@ t = bigint.tobytes(len(s), byteorder=byteorder, signed=signed) assert s == t +def test_gcd(self): +assert gcd_binary(2*3*7**2, 2**2*7) == 2*7 +assert gcd_binary(-2*3*7**2, 2**2*7) == 2*7 +assert gcd_binary(2*3*7**2, -2**2*7) == 2*7 +assert gcd_binary(-2*3*7**2, -2**2*7) == 2*7 +assert gcd_binary(1234, 5678) == 2 +assert gcd_binary(13, 13**6) == 13 +assert gcd_binary(12, 0) == 12 +assert gcd_binary(0, 0) == 0 + +x = rbigint.fromlong(9969216677189303386214405760200) +y = rbigint.fromlong(16130531424904581415797907386349) +g = x.gcd(y) +assert g == rbigint.fromlong(1) + +for x in gen_signs([12843440367927679363613699686751681643652809878241019930204617606850071260822269719878805]): +x = rbigint.fromlong(x) +for y in gen_signs([12372280584571061381380725743231391746505148712246738812788540537514927882776203827701778968535]): +y = rbigint.fromlong(y) +g = x.gcd(y) +assert g.tolong() == 18218089570126697993340888567155155527541105
[pypy-commit] pypy py3.6: merge default
Author: Carl Friedrich Bolz-Tereick Branch: py3.6 Changeset: r96958:5a7ab6765acf Date: 2019-07-10 13:38 +0200 http://bitbucket.org/pypy/pypy/changeset/5a7ab6765acf/ Log:merge default diff --git a/rpython/jit/backend/arm/assembler.py b/rpython/jit/backend/arm/assembler.py --- a/rpython/jit/backend/arm/assembler.py +++ b/rpython/jit/backend/arm/assembler.py @@ -532,26 +532,22 @@ def gen_shadowstack_header(self, gcrootmap): # lr = shadow stack top addr -# r4 = *lr +# ip = *lr rst = gcrootmap.get_root_stack_top_addr() self.mc.gen_load_int(r.lr.value, rst) -self.load_reg(self.mc, r.r4, r.lr) -# *r4 = 1 -# the '1' is to benefit from the shadowstack 'is_minor' optimization -self.mc.gen_load_int(r.ip.value, 1) -self.store_reg(self.mc, r.ip, r.r4) -# *(r4+WORD) = r.fp -self.store_reg(self.mc, r.fp, r.r4, WORD) +self.load_reg(self.mc, r.ip, r.lr) +# *ip = r.fp +self.store_reg(self.mc, r.fp, r.ip) # -self.mc.ADD_ri(r.r4.value, r.r4.value, 2 * WORD) -# *lr = r4 + 2 * WORD -self.store_reg(self.mc, r.r4, r.lr) +self.mc.ADD_ri(r.ip.value, r.ip.value, WORD) +# *lr = ip + WORD +self.store_reg(self.mc, r.ip, r.lr) def gen_footer_shadowstack(self, gcrootmap, mc): rst = gcrootmap.get_root_stack_top_addr() mc.gen_load_int(r.ip.value, rst) self.load_reg(mc, r.r4, r.ip) -mc.SUB_ri(r.r4.value, r.r4.value, 2 * WORD) +mc.SUB_ri(r.r4.value, r.r4.value, WORD) self.store_reg(mc, r.r4, r.ip) def _dump(self, ops, type='loop'): diff --git a/rpython/jit/backend/arm/regalloc.py b/rpython/jit/backend/arm/regalloc.py --- a/rpython/jit/backend/arm/regalloc.py +++ b/rpython/jit/backend/arm/regalloc.py @@ -373,6 +373,10 @@ if box.type == REF and self.rm.is_still_alive(box): assert not noregs assert loc.is_core_reg() +#val = self.cpu.all_reg_indexes[loc.value] +# ^^^ That is the correct way to write it down, but as a +# special case in the arm backend only, this is equivalent +# to just the line below: val = loc.value gcmap[val // WORD // 8] |= r_uint(1) << (val % (WORD * 8)) for box, loc in self.fm.bindings.iteritems(): diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -1423,6 +1423,12 @@ bits = ovfcheck((i-1) * SHIFT) + msd_bits return bits +def gcd(self, other): +""" Compute the (always positive) greatest common divisor of self and +other """ +return gcd_lehmer(self.abs(), other.abs()) + + def __repr__(self): return "" % (self._digits, self.sign, self.numdigits(), len(self._digits), @@ -2960,3 +2966,88 @@ z.setdigit(pdigit, accum) z._normalize() return z + + +def gcd_binary(a, b): +if a == 0: +return b + +if b == 0: +return a + +a, b = abs(a), abs(b) + +shift = 0 +while (a | b) & 1 == 0: +a >>= 1 +b >>= 1 +shift += 1 + +while a & 1 == 0: +a >>= 1 + +while b & 1 == 0: +b >>= 1 + +while a != b: +a, b = abs(a - b), min(a, b) +while a & 1 == 0: +a >>= 1 + +return a << shift + +def lehmer_xgcd(a, b): +s_old, s_new = 1, 0 +t_old, t_new = 0, 1 +while b >> (SHIFT >> 1): +q, r = a // b, a % b + +a, b = b, r +s_old, s_new = s_new, s_old - q * s_new +t_old, t_new = t_new, t_old - q * t_new + +return s_old, t_old, s_new, t_new + +def gcd_lehmer(a, b): +if a.lt(b): +a, b = b, a + +while b.size > 1: +a_ms = a.digit(a.size-1) + +x = 0 +while a_ms & (0xFF << SHIFT-8) == 0: +a_ms <<= 8 +x += 8 + +while a_ms & (1 << SHIFT-1) == 0: +a_ms <<= 1 +x += 1 + +a_ms |= a.digit(a.size-2) >> SHIFT-x + +if a.size == b.size: +b_ms = (b.digit(b.size-1) << x) | (b.digit(b.size-2) >> SHIFT-x) +elif a.size == b.size+1: +b_ms = b.digit(b.size-1) >> SHIFT-x +else: +b_ms = 0 + +if b_ms >> (SHIFT+1 >> 1) == 0: +a, b = b, a.mod(b) +continue + +s_old, t_old, s_new, t_new = lehmer_xgcd(a_ms, b_ms) + +n_a = a.int_mul(s_new).add(b.int_mul(t_new)).abs() +b = a.int_mul(s_old).add(b.int_mul(t_old)).abs() +a = n_a + +if a.lt(b): +a, b = b, a + +if not b.tobool(): +return a + +a = a.mod(b) +return rbigint.fromint(gcd_binary(b.toint(), a.toint())) diff --git a/rpython/rlib/test/test_rbigint.py b/rpython/rlib/test/test_rbigint.py --- a/rpython/rli
[pypy-commit] pypy py3.6: ~1% speedup to GCD.
Author: Stian Andreassen Branch: py3.6 Changeset: r96961:ab71ab09aca2 Date: 2019-07-10 22:41 +0200 http://bitbucket.org/pypy/pypy/changeset/ab71ab09aca2/ Log:~1% speedup to GCD. diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -3013,7 +3013,7 @@ a, b = b, a while b.size > 1: -a_ms = a.digit(a.size-1) +a_ms = a.digit(abs(a.size-1)) x = 0 while a_ms & (0xFF << SHIFT-8) == 0: @@ -3024,12 +3024,12 @@ a_ms <<= 1 x += 1 -a_ms |= a.digit(a.size-2) >> SHIFT-x +a_ms |= a.digit(abs(a.size-2)) >> SHIFT-x if a.size == b.size: -b_ms = (b.digit(b.size-1) << x) | (b.digit(b.size-2) >> SHIFT-x) +b_ms = (b.digit(abs(b.size-1)) << x) | (b.digit(abs(b.size-2)) >> SHIFT-x) elif a.size == b.size+1: -b_ms = b.digit(b.size-1) >> SHIFT-x +b_ms = b.digit(abs(b.size-1)) >> SHIFT-x else: b_ms = 0 ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
