[pypy-commit] pypy default: or_ to int_or_ in immutable_unique_id
Author: stian Branch: Changeset: r76960:5a9239033d07 Date: 2015-05-01 15:56 +0200 http://bitbucket.org/pypy/pypy/changeset/5a9239033d07/ Log:or_ to int_or_ in immutable_unique_id diff --git a/pypy/objspace/std/complexobject.py b/pypy/objspace/std/complexobject.py --- a/pypy/objspace/std/complexobject.py +++ b/pypy/objspace/std/complexobject.py @@ -270,7 +270,7 @@ imag = space.float_w(space.getattr(self, space.wrap("imag"))) real_b = rbigint.fromrarith_int(float2longlong(real)) imag_b = rbigint.fromrarith_int(r_ulonglong(float2longlong(imag))) -val = real_b.lshift(64).or_(imag_b).lshift(3).or_(rbigint.fromint(tag)) +val = real_b.lshift(64).or_(imag_b).lshift(3).int_or_(tag) return space.newlong_from_rbigint(val) def int(self, space): diff --git a/pypy/objspace/std/floatobject.py b/pypy/objspace/std/floatobject.py --- a/pypy/objspace/std/floatobject.py +++ b/pypy/objspace/std/floatobject.py @@ -185,7 +185,7 @@ from pypy.objspace.std.util import IDTAG_FLOAT as tag val = float2longlong(space.float_w(self)) b = rbigint.fromrarith_int(val) -b = b.lshift(3).or_(rbigint.fromint(tag)) +b = b.lshift(3).int_or_(tag) return space.newlong_from_rbigint(b) def __repr__(self): diff --git a/pypy/objspace/std/intobject.py b/pypy/objspace/std/intobject.py --- a/pypy/objspace/std/intobject.py +++ b/pypy/objspace/std/intobject.py @@ -46,7 +46,7 @@ if self.user_overridden_class: return None b = space.bigint_w(self) -b = b.lshift(3).or_(rbigint.fromint(IDTAG_INT)) +b = b.lshift(3).int_or_(IDTAG_INT) return space.newlong_from_rbigint(b) def int(self, space): diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py --- a/pypy/objspace/std/longobject.py +++ b/pypy/objspace/std/longobject.py @@ -45,7 +45,7 @@ if self.user_overridden_class: return None b = space.bigint_w(self) -b = b.lshift(3).or_(rbigint.fromint(IDTAG_LONG)) +b = b.lshift(3).int_or_(IDTAG_LONG) return space.newlong_from_rbigint(b) def unwrap(self, space): ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy default: Merge
Author: stian Branch: Changeset: r76973:df47fcbdecf4 Date: 2015-05-02 02:38 +0200 http://bitbucket.org/pypy/pypy/changeset/df47fcbdecf4/ Log:Merge diff --git a/rpython/jit/backend/llsupport/llerrno.py b/rpython/jit/backend/llsupport/llerrno.py --- a/rpython/jit/backend/llsupport/llerrno.py +++ b/rpython/jit/backend/llsupport/llerrno.py @@ -40,6 +40,13 @@ assert nerrno >= 0 cpu._debug_errno_container[5] = nerrno +def get_debug_saved_altlasterror(cpu): +return cpu._debug_errno_container[6] + +def set_debug_saved_altlasterror(cpu, nerrno): +assert nerrno >= 0 +cpu._debug_errno_container[6] = nerrno + def get_rpy_lasterror_offset(cpu): if cpu.translate_support_code: from rpython.rlib import rthread diff --git a/rpython/jit/backend/test/runner_test.py b/rpython/jit/backend/test/runner_test.py --- a/rpython/jit/backend/test/runner_test.py +++ b/rpython/jit/backend/test/runner_test.py @@ -3106,15 +3106,22 @@ self.cpu.compile_loop(inputargs, ops, looptoken) # llerrno.set_debug_saved_lasterror(self.cpu, 24) +llerrno.set_debug_saved_altlasterror(self.cpu, 25) deadframe = self.cpu.execute_token(looptoken, 9, 8, 7, 6, 5, 4, 3) original_result = self.cpu.get_int_value(deadframe, 0) result = llerrno.get_debug_saved_lasterror(self.cpu) -print 'saveerr =', saveerr, ': got result =', result +altresult = llerrno.get_debug_saved_altlasterror(self.cpu) +print 'saveerr =', saveerr, ': got result =', result, +print 'and altresult =', altresult # -if saveerr == rffi.RFFI_SAVE_LASTERROR: -assert result == 42 # from the C code +if saveerr & rffi.RFFI_SAVE_LASTERROR: +# one from the C code, the other not touched +if saveerr & rffi.RFFI_ALT_ERRNO: +assert (result, altresult) == (24, 42) +else: +assert (result, altresult) == (42, 25) else: -assert result == 24 # not touched +assert (result, altresult) == (24, 25) # not touched assert original_result == 3456789 def test_call_release_gil_readsaved_lasterror(self): @@ -3169,11 +3176,17 @@ self.cpu.compile_loop(inputargs, ops, looptoken) # llerrno.set_debug_saved_lasterror(self.cpu, 24) +llerrno.set_debug_saved_altlasterror(self.cpu, 25) deadframe = self.cpu.execute_token(looptoken, 9, 8, 7, 6, 5, 4, 3) result = self.cpu.get_int_value(deadframe, 0) assert llerrno.get_debug_saved_lasterror(self.cpu) == 24 +assert llerrno.get_debug_saved_altlasterror(self.cpu) == 25 # -assert result == 24 + 345678900 +if saveerr & rffi.RFFI_ALT_ERRNO: +expected_lasterror = 25 +else: +expected_lasterror = 24 +assert result == expected_lasterror + 345678900 def test_call_release_gil_err_all(self): from rpython.translator.tool.cbuild import ExternalCompilationInfo @@ -3228,7 +3241,6 @@ for saveerr in [rffi.RFFI_ERR_ALL, rffi.RFFI_ERR_ALL | rffi.RFFI_ALT_ERRNO, ]: -use_alt_errno = saveerr & rffi.RFFI_ALT_ERRNO faildescr = BasicFailDescr(1) inputargs = [BoxInt() for i in range(7)] i1 = BoxInt() @@ -3244,7 +3256,7 @@ looptoken = JitCellToken() self.cpu.compile_loop(inputargs, ops, looptoken) # -if use_alt_errno: +if saveerr & rffi.RFFI_ALT_ERRNO: llerrno.set_debug_saved_alterrno(self.cpu, 8) else: llerrno.set_debug_saved_errno(self.cpu, 8) diff --git a/rpython/jit/backend/x86/callbuilder.py b/rpython/jit/backend/x86/callbuilder.py --- a/rpython/jit/backend/x86/callbuilder.py +++ b/rpython/jit/backend/x86/callbuilder.py @@ -221,6 +221,7 @@ mc.CALL(imm(follow_jump(SetLastError_addr))) # restore the stack position without assuming a particular # calling convention of _SetLastError() +self.mc.stack_frame_size_delta(-WORD) self.mc.MOV(esp, self.saved_stack_position_reg) if save_err & rffi.RFFI_READSAVED_ERRNO: diff --git a/rpython/rlib/jit.py b/rpython/rlib/jit.py --- a/rpython/rlib/jit.py +++ b/rpython/rlib/jit.py @@ -34,6 +34,26 @@ side effect, but those side effects are idempotent (ie caching). If a particular call to this function ends up raising an exception, then it is handled like a normal function call (this decorator is ignored). + +Note also that this optimisation will only take effect if the arguments +t
[pypy-commit] pypy default: Use int with rbigint operations. This provide a upto 25% speedup on such operations, and a minor 5% speedup on pidigits.
Author: stian Branch: Changeset: r76972:f01fd6fb3a45 Date: 2015-05-02 02:37 +0200 http://bitbucket.org/pypy/pypy/changeset/f01fd6fb3a45/ Log:Use int with rbigint operations. This provide a upto 25% speedup on such operations, and a minor 5% speedup on pidigits. diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py --- a/pypy/objspace/std/longobject.py +++ b/pypy/objspace/std/longobject.py @@ -350,8 +350,13 @@ def _make_descr_cmp(opname): op = getattr(rbigint, opname) -@delegate_other +intop = getattr(rbigint, "int_" + opname) + def descr_impl(self, space, w_other): +if isinstance(w_other, W_AbstractIntObject): +return space.newbool(intop(self.num, w_other.int_w(space))) +elif not isinstance(w_other, W_AbstractLongObject): +return space.w_NotImplemented return space.newbool(op(self.num, w_other.asbigint())) return func_with_new_name(descr_impl, "descr_" + opname) @@ -362,7 +367,7 @@ descr_gt = _make_descr_cmp('gt') descr_ge = _make_descr_cmp('ge') -def _make_generic_descr_binop(opname): +def _make_generic_descr_binop_noncommutative(opname): methname = opname + '_' if opname in ('and', 'or') else opname descr_rname = 'descr_r' + opname op = getattr(rbigint, methname) @@ -372,33 +377,65 @@ def descr_binop(self, space, w_other): return W_LongObject(op(self.num, w_other.asbigint())) -if opname in COMMUTATIVE_OPS: -@func_renamer(descr_rname) -def descr_rbinop(self, space, w_other): -return descr_binop(self, space, w_other) -else: -@func_renamer(descr_rname) -@delegate_other -def descr_rbinop(self, space, w_other): -return W_LongObject(op(w_other.asbigint(), self.num)) +@func_renamer(descr_rname) +@delegate_other +def descr_rbinop(self, space, w_other): +return W_LongObject(op(w_other.asbigint(), self.num)) return descr_binop, descr_rbinop +def _make_generic_descr_binop(opname): +if opname not in COMMUTATIVE_OPS: +raise Exception("Not supported") + +methname = opname + '_' if opname in ('and', 'or') else opname +descr_rname = 'descr_r' + opname +op = getattr(rbigint, methname) +intop = getattr(rbigint, "int_" + methname) + +@func_renamer('descr_' + opname) +def descr_binop(self, space, w_other): +if isinstance(w_other, W_AbstractIntObject): +return W_LongObject(intop(self.num, w_other.int_w(space))) +elif not isinstance(w_other, W_AbstractLongObject): +return space.w_NotImplemented + +return W_LongObject(op(self.num, w_other.asbigint())) + +@func_renamer(descr_rname) +def descr_rbinop(self, space, w_other): +if isinstance(w_other, W_AbstractIntObject): +return W_LongObject(intop(self.num, w_other.int_w(space))) +elif not isinstance(w_other, W_AbstractLongObject): +return space.w_NotImplemented + +return W_LongObject(op(w_other.asbigint(), self.num)) + +return descr_binop, descr_rbinop + descr_add, descr_radd = _make_generic_descr_binop('add') -descr_sub, descr_rsub = _make_generic_descr_binop('sub') +descr_sub, descr_rsub = _make_generic_descr_binop_noncommutative('sub') descr_mul, descr_rmul = _make_generic_descr_binop('mul') descr_and, descr_rand = _make_generic_descr_binop('and') descr_or, descr_ror = _make_generic_descr_binop('or') descr_xor, descr_rxor = _make_generic_descr_binop('xor') -def _make_descr_binop(func): +def _make_descr_binop(func, int_func=None): opname = func.__name__[1:] -@delegate_other -@func_renamer('descr_' + opname) -def descr_binop(self, space, w_other): -return func(self, space, w_other) - +if int_func: +@func_renamer('descr_' + opname) +def descr_binop(self, space, w_other): +if isinstance(w_other, W_AbstractIntObject): +return int_func(self, space, w_other.int_w(space)) +elif not isinstance(w_other, W_AbstractLongObject): +return space.w_NotImplemented +return func(self, space, w_other) +else: +@delegate_other +@func_renamer('descr_' + opname) +def descr_binop(self, space, w_other): +return func(self, space, w_other)
[pypy-commit] pypy math-improvements: Merge default
Author: stian Branch: math-improvements Changeset: r95240:8679952ae1fd Date: 2018-10-25 13:55 +0200 http://bitbucket.org/pypy/pypy/changeset/8679952ae1fd/ Log:Merge default diff too long, truncating to 2000 out of 44960 lines diff --git a/.hgtags b/.hgtags --- a/.hgtags +++ b/.hgtags @@ -33,7 +33,12 @@ 050d84dd78997f021acf0e133934275d63547cc0 release-pypy2.7-v5.4.1 050d84dd78997f021acf0e133934275d63547cc0 release-pypy2.7-v5.4.1 0e2d9a73f5a1818d0245d75daccdbe21b2d5c3ef release-pypy2.7-v5.4.1 +4909c06daf41ce88f87dc01c57959cadad4df4a8 RevDB-pypy2.7-v5.4.1 +4909c06daf41ce88f87dc01c57959cadad4df4a8 RevDB-pypy2.7-v5.4.1 +d7724c0a5700b895a47de44074cdf5fd659a988f RevDB-pypy2.7-v5.4.1 aff251e543859ce4508159dd9f1a82a2f553de00 release-pypy2.7-v5.6.0 +e90317857d27917bf840caf675832292ee070510 RevDB-pypy2.7-v5.6.1 +a24d6c7000c8099c73d3660857f7e3cee5ac045c RevDB-pypy2.7-v5.6.2 fa3249d55d15b9829e1be69cdf45b5a44cec902d release-pypy2.7-v5.7.0 b16a4363e930f6401bceb499b9520955504c6cb0 release-pypy3.5-v5.7.0 1aa2d8e03cdfab54b7121e93fda7e98ea88a30bf release-pypy2.7-v5.7.1 @@ -51,3 +56,5 @@ release-pypy3.5-v5.10.0 09f9160b643e3f02ccb8c843b2fbb4e5cbf54082 release-pypy3.5-v5.10.0 3f6eaa010fce78cc7973bdc1dfdb95970f08fed2 release-pypy3.5-v5.10.1 +ab0b9caf307db6592905a80b8faffd69b39005b8 release-pypy2.7-v6.0.0 +fdd60ed87e941677e8ea11acf9f1819466521bf2 release-pypy3.5-v6.0.0 diff --git a/LICENSE b/LICENSE --- a/LICENSE +++ b/LICENSE @@ -6,36 +6,36 @@ Except when otherwise stated (look for LICENSE files in directories or information at the beginning of each file) all software and documentation in the 'rpython', 'pypy', 'ctype_configure', 'dotviewer', 'demo', 'lib_pypy', -'py', and '_pytest' directories is licensed as follows: +'py', and '_pytest' directories is licensed as follows: The MIT License -Permission is hereby granted, free of charge, to any person -obtaining a copy of this software and associated documentation -files (the "Software"), to deal in the Software without -restriction, including without limitation the rights to use, -copy, modify, merge, publish, distribute, sublicense, and/or -sell copies of the Software, and to permit persons to whom the +Permission is hereby granted, free of charge, to any person +obtaining a copy of this software and associated documentation +files (the "Software"), to deal in the Software without +restriction, including without limitation the rights to use, +copy, modify, merge, publish, distribute, sublicense, and/or +sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: -The above copyright notice and this permission notice shall be included +The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS -OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL -THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING -FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS +OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL +THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. PyPy Copyright holders 2003-2018 + Except when otherwise stated (look for LICENSE files or information at the beginning of each file) the files in the 'pypy' directory are each -copyrighted by one or more of the following people and organizations: +copyrighted by one or more of the following people and organizations: Armin Rigo Maciej Fijalkowski @@ -89,13 +89,13 @@ Niko Matsakis Alexander Hesse Ludovic Aubry + stian Jacob Hallen Jason Creighton Mark Young Alex Martelli Spenser Bauman Michal Bendowski - stian Jan de Mooij Tyler Wade Vincent Legoll @@ -123,10 +123,10 @@ Wenzhu Man Konstantin Lopuhin John Witulski + Jeremy Thurgood Greg Price Ivan Sichmann Freitas Dario Bertini - Jeremy Thurgood Mark Pearse Simon Cross Tobias Pape @@ -145,18 +145,19 @@
[pypy-commit] pypy math-improvements: Simplefy code
Author: stian Branch: math-improvements Changeset: r95267:e7232ea18ab2 Date: 2018-11-01 10:33 +0100 http://bitbucket.org/pypy/pypy/changeset/e7232ea18ab2/ Log:Simplefy code diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -588,29 +588,7 @@ # Fallback to Long. return self.lt(rbigint.fromint(other)) -osign = 1 -if other == 0: -osign = 0 -elif other < 0: -osign = -1 - -if self.sign > osign: -return False -elif self.sign < osign: -return True - -digits = self.numdigits() - -if digits > 1: -if osign == 1: -return False -else: -return True - -d1 = self.sign * self.digit(0) -if d1 < other: -return True -return False +return _x_int_lt(self, other, False) def le(self, other): return not other.lt(self) @@ -622,29 +600,7 @@ # Fallback to Long. return self.lt(rbigint.fromint(other)) -osign = 1 -if other == 0: -osign = 0 -elif other < 0: -osign = -1 - -if self.sign > osign: -return False -elif self.sign < osign: -return True - -digits = self.numdigits() - -if digits > 1: -if osign == 1: -return False -else: -return True - -d1 = self.sign * self.digit(0) -if d1 <= other: -return True -return False +return _x_int_lt(self, other, True) def gt(self, other): return other.lt(self) @@ -2186,6 +2142,36 @@ rem.sign = - rem.sign return z, rem +def _x_int_lt(a, b, eq=False): +""" Compare bigint a with int b for less than or less than or equal """ +osign = 1 +if b == 0: +osign = 0 +elif b < 0: +osign = -1 + +if a.sign > osign: +return False +elif a.sign < osign: +return True + +digits = a.numdigits() + +if digits > 1: +if osign == 1: +return False +else: +return True + +d1 = a.sign * a.digit(0) +if eq: +if d1 <= b: +return True +else: +if d1 < b: +return True +return False + # __ conversions to double ___ def _AsScaledDouble(v): ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Fix for issue #2946 ?
Author: stian Branch: math-improvements Changeset: r95882:9bb63f07b007 Date: 2019-02-07 12:13 +0100 http://bitbucket.org/pypy/pypy/changeset/9bb63f07b007/ Log:Fix for issue #2946 ? diff --git a/pypy/objspace/std/intobject.py b/pypy/objspace/std/intobject.py --- a/pypy/objspace/std/intobject.py +++ b/pypy/objspace/std/intobject.py @@ -506,8 +506,14 @@ try: result = _pow(space, x, y, z) -except (OverflowError, ValueError): +except OverflowError: return _pow_ovf2long(space, x, self, y, w_exponent, w_modulus) +except ValueError: +# float result, so let avoid a roundtrip in rbigint. +self = self.descr_float(space) +w_exponent = w_exponent.descr_float(space) +return space.pow(self, w_exponent, space.w_None) + return space.newint(result) @unwrap_spec(w_modulus=WrappedDefault(None)) ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy py3-bigint-to-int: Branch to experiement with making bigints into ints whenever they fit
Author: stian Branch: py3-bigint-to-int Changeset: r96055:d84813084f47 Date: 2019-02-18 14:35 +0100 http://bitbucket.org/pypy/pypy/changeset/d84813084f47/ Log:Branch to experiement with making bigints into ints whenever they fit ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy py3-bigint-to-int: Code and test for most ops
Author: stian Branch: py3-bigint-to-int Changeset: r96056:517a32bab8f7 Date: 2019-02-18 15:08 +0100 http://bitbucket.org/pypy/pypy/changeset/517a32bab8f7/ Log:Code and test for most ops diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py --- a/pypy/objspace/std/longobject.py +++ b/pypy/objspace/std/longobject.py @@ -236,11 +236,14 @@ def descr_sub(self, space, w_other): if isinstance(w_other, W_IntObject): -return W_LongObject(self.num.int_sub(w_other.int_w(space))) +res = self.num.int_sub(w_other.int_w(space)) elif not isinstance(w_other, W_AbstractLongObject): return space.w_NotImplemented -return W_LongObject(self.num.sub(w_other.asbigint())) - +res = self.num.sub(w_other.asbigint()) +try: +return W_IntObject(res.toint()) +except OverflowError: +return W_LongObject(res) @delegate_other def descr_rsub(self, space, w_other): return W_LongObject(w_other.asbigint().sub(self.num)) @@ -257,21 +260,29 @@ @func_renamer('descr_' + opname) def descr_binop(self, space, w_other): if isinstance(w_other, W_IntObject): -return W_LongObject(intop(self.num, w_other.int_w(space))) +res = intop(self.num, w_other.int_w(space)) elif not isinstance(w_other, W_AbstractLongObject): return space.w_NotImplemented - -return W_LongObject(op(self.num, w_other.asbigint())) +else: +res = op(self.num, w_other.asbigint()) +try: +return W_IntObject(res.toint()) +except OverflowError: +return W_LongObject(res) @func_renamer(descr_rname) def descr_rbinop(self, space, w_other): if isinstance(w_other, W_IntObject): -return W_LongObject(intop(self.num, w_other.int_w(space))) +res = intop(self.num, w_other.int_w(space)) elif not isinstance(w_other, W_AbstractLongObject): return space.w_NotImplemented - -return W_LongObject(op(w_other.asbigint(), self.num)) - +else: +res = op(w_other.asbigint(), self.num) +try: +return W_IntObject(res.toint()) +except OverflowError: +return W_LongObject(res) + return descr_binop, descr_rbinop descr_add, descr_radd = _make_generic_descr_binop('add') @@ -340,7 +351,11 @@ except ZeroDivisionError: raise oefmt(space.w_ZeroDivisionError, "long division or modulo by zero") -return newlong(space, z) + +try: +return space.newint(z.toint()) +except OverflowError: +return newlong(space, z) def _int_floordiv(self, space, other): try: @@ -357,7 +372,10 @@ except ZeroDivisionError: raise oefmt(space.w_ZeroDivisionError, "integer division or modulo by zero") -return newlong(space, z) +try: +return space.newint(z.toint()) +except OverflowError: +return newlong(space, z) def _int_mod(self, space, other): try: @@ -365,7 +383,10 @@ except ZeroDivisionError: raise oefmt(space.w_ZeroDivisionError, "long division or modulo by zero") -return newlong(space, z) + +# Int mod should always fit into an int. +return space.newint(z.toint()) +#return newlong(space, z) descr_mod, descr_rmod = _make_descr_binop(_mod, _int_mod) def _divmod(self, space, w_other): diff --git a/pypy/objspace/std/test/test_longobject.py b/pypy/objspace/std/test/test_longobject.py --- a/pypy/objspace/std/test/test_longobject.py +++ b/pypy/objspace/std/test/test_longobject.py @@ -1,6 +1,7 @@ # -*- encoding: utf-8 -*- import py from pypy.objspace.std import longobject as lobj +from pypy.objspace.std import intobject as iobj from rpython.rlib.rbigint import rbigint class TestW_LongObject: @@ -38,7 +39,21 @@ w_obj = space.newlong_from_rarith_int(r(x)) assert space.bigint_w(w_obj).eq(rbigint.fromlong(x)) - +def test_long_to_int(self): +a = lobj.W_LongObject.fromlong(8) +b = lobj.W_LongObject.fromlong(1) + +floordivres = a._floordiv(self.space, b) +assert type(floordivres) is iobj.W_IntObject + +modres = a._mod(self.space, b) +assert type(modres) is iobj.W_IntObject + +addres = a.descr_add(self.space, b) +assert type(addres) is iobj.W_IntObject + +subres = a.descr_sub(self.space, b) +assert type(subres) is iobj.W_IntObjec
[pypy-commit] pypy py3-bigint-to-int: More ops
Author: stian Branch: py3-bigint-to-int Changeset: r96057:daa9f9b2439b Date: 2019-02-18 15:16 +0100 http://bitbucket.org/pypy/pypy/changeset/daa9f9b2439b/ Log:More ops diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py --- a/pypy/objspace/std/longobject.py +++ b/pypy/objspace/std/longobject.py @@ -246,7 +246,11 @@ return W_LongObject(res) @delegate_other def descr_rsub(self, space, w_other): -return W_LongObject(w_other.asbigint().sub(self.num)) +res = w_other.asbigint().sub(self.num) +try: +return W_IntObject(res.toint()) +except OverflowError: +return W_LongObject(res) def _make_generic_descr_binop(opname): if opname not in COMMUTATIVE_OPS: @@ -320,12 +324,20 @@ shift = w_other.asbigint().toint() except OverflowError: # b too big raise oefmt(space.w_OverflowError, "shift count too large") -return W_LongObject(self.num.lshift(shift)) - +res = self.num.lshift(shift) +try: +return W_IntObject(res.toint()) +except OverflowError: +return W_LongObject(res) + def _int_lshift(self, space, other): if other < 0: raise oefmt(space.w_ValueError, "negative shift count") -return W_LongObject(self.num.lshift(other)) +res = self.num.lshift(other) +try: +return W_IntObject(res.toint()) +except OverflowError: +return W_LongObject(res) descr_lshift, descr_rlshift = _make_descr_binop(_lshift, _int_lshift) @@ -336,13 +348,20 @@ shift = w_other.asbigint().toint() except OverflowError: # b too big # XXX maybe just return 0L instead? raise oefmt(space.w_OverflowError, "shift count too large") -return newlong(space, self.num.rshift(shift)) +res = self.num.rshift(shift) +try: +return space.newint(res.toint()) +except OverflowError: +return newlong(space, res) def _int_rshift(self, space, other): if other < 0: raise oefmt(space.w_ValueError, "negative shift count") - -return newlong(space, self.num.rshift(other)) +res = self.num.rshift(other) +try: +return space.newint(res.toint()) +except OverflowError: +return newlong(space, res) descr_rshift, descr_rrshift = _make_descr_binop(_rshift, _int_rshift) def _floordiv(self, space, w_other): ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy py3-bigint-to-int: Add tests for more ops
Author: stian Branch: py3-bigint-to-int Changeset: r96058:521850d02e44 Date: 2019-02-18 15:38 +0100 http://bitbucket.org/pypy/pypy/changeset/521850d02e44/ Log:Add tests for more ops diff --git a/pypy/objspace/std/test/test_longobject.py b/pypy/objspace/std/test/test_longobject.py --- a/pypy/objspace/std/test/test_longobject.py +++ b/pypy/objspace/std/test/test_longobject.py @@ -49,11 +49,22 @@ modres = a._mod(self.space, b) assert type(modres) is iobj.W_IntObject +# Covers all of descr_binop? addres = a.descr_add(self.space, b) assert type(addres) is iobj.W_IntObject +# Covers all of descr_rbinop? +raddres = a.descr_radd(self.space, b) +assert type(raddres) is iobj.W_IntObject + subres = a.descr_sub(self.space, b) assert type(subres) is iobj.W_IntObject + +lshiftres = a._lshift(self.space, b) +assert type(lshiftres) is iobj.W_IntObject + +rshiftres = a._rshift(self.space, b) +assert type(rshiftres) is iobj.W_IntObject class AppTestLong: def w__long(self, obj): ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy py3-bigint-to-int: Reduce this to int_mod and int_and ops for now.
Author: stian Branch: py3-bigint-to-int Changeset: r96071:4e3d4c68bcde Date: 2019-02-18 16:49 +0100 http://bitbucket.org/pypy/pypy/changeset/4e3d4c68bcde/ Log:Reduce this to int_mod and int_and ops for now. diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py --- a/pypy/objspace/std/longobject.py +++ b/pypy/objspace/std/longobject.py @@ -234,23 +234,22 @@ descr_gt = _make_descr_cmp('gt') descr_ge = _make_descr_cmp('ge') -def descr_sub(self, space, w_other): -if isinstance(w_other, W_IntObject): -res = self.num.int_sub(w_other.int_w(space)) -elif not isinstance(w_other, W_AbstractLongObject): -return space.w_NotImplemented -res = self.num.sub(w_other.asbigint()) -try: -return W_IntObject(res.toint()) -except OverflowError: -return W_LongObject(res) -@delegate_other -def descr_rsub(self, space, w_other): -res = w_other.asbigint().sub(self.num) -try: -return W_IntObject(res.toint()) -except OverflowError: -return W_LongObject(res) +def _make_generic_descr_binop_noncommutative(opname): +methname = opname + '_' if opname in ('and', 'or') else opname +descr_rname = 'descr_r' + opname +op = getattr(rbigint, methname) + +@func_renamer('descr_' + opname) +@delegate_other +def descr_binop(self, space, w_other): +return W_LongObject(op(self.num, w_other.asbigint())) + +@func_renamer(descr_rname) +@delegate_other +def descr_rbinop(self, space, w_other): +return W_LongObject(op(w_other.asbigint(), self.num)) + +return descr_binop, descr_rbinop def _make_generic_descr_binop(opname): if opname not in COMMUTATIVE_OPS: @@ -264,49 +263,82 @@ @func_renamer('descr_' + opname) def descr_binop(self, space, w_other): if isinstance(w_other, W_IntObject): -res = intop(self.num, w_other.int_w(space)) +return W_LongObject(intop(self.num, w_other.int_w(space))) elif not isinstance(w_other, W_AbstractLongObject): return space.w_NotImplemented -else: -res = op(self.num, w_other.asbigint()) -try: -return W_IntObject(res.toint()) -except OverflowError: -return W_LongObject(res) + +return W_LongObject(op(self.num, w_other.asbigint())) + +@func_renamer(descr_rname) +def descr_rbinop(self, space, w_other): +if isinstance(w_other, W_IntObject): +return W_LongObject(intop(self.num, w_other.int_w(space))) +elif not isinstance(w_other, W_AbstractLongObject): +return space.w_NotImplemented + +return W_LongObject(op(w_other.asbigint(), self.num)) + +return descr_binop, descr_rbinop + +def _make_generic_descr_binop_maybeint(opname): +if opname not in COMMUTATIVE_OPS: +raise Exception("Not supported") + +methname = opname + '_' if opname in ('and', 'or') else opname +descr_rname = 'descr_r' + opname +op = getattr(rbigint, methname) +intop = getattr(rbigint, "int_" + methname) + +@func_renamer('descr_' + opname) +def descr_binop(self, space, w_other): +if isinstance(w_other, W_IntObject): +res = intop(self.num, w_other.int_w(space)) +try: +return W_IntObject(res.toint()) +except OverflowError: +return W_LongObject(res) +elif not isinstance(w_other, W_AbstractLongObject): +return space.w_NotImplemented + +return W_LongObject(op(self.num, w_other.asbigint())) @func_renamer(descr_rname) def descr_rbinop(self, space, w_other): if isinstance(w_other, W_IntObject): res = intop(self.num, w_other.int_w(space)) +try: +return W_IntObject(res.toint()) +except OverflowError: +return W_LongObject(res) elif not isinstance(w_other, W_AbstractLongObject): return space.w_NotImplemented -else: -res = op(w_other.asbigint(), self.num) -try: -return W_IntObject(res.toint()) -except OverflowError: -return W_LongObject(res) - + +return W_LongObject(op(w_other.asbigint(), self.num)) + return descr_binop, descr_rbinop - descr_add, descr_radd = _make_generic_descr_binop('add') - +descr_sub, descr_rsub = _make_generic_descr_binop_noncommutati
[pypy-commit] pypy default: Add missing int_floordiv, int_divmod. Improves pidigits by about 5%
Author: stian Branch: Changeset: r92789:d420391a020a Date: 2017-10-18 17:48 +0200 http://bitbucket.org/pypy/pypy/changeset/d420391a020a/ Log:Add missing int_floordiv, int_divmod. Improves pidigits by about 5% diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py --- a/pypy/objspace/std/longobject.py +++ b/pypy/objspace/std/longobject.py @@ -491,17 +491,18 @@ "long division or modulo by zero") return newlong(space, z) -def _floordiv(self, space, w_other): +def _int_floordiv(self, space, w_other): try: -z = self.num.floordiv(w_other.asbigint()) +z = self.num.int_floordiv(w_other) except ZeroDivisionError: raise oefmt(space.w_ZeroDivisionError, "long division or modulo by zero") return newlong(space, z) -descr_floordiv, descr_rfloordiv = _make_descr_binop(_floordiv) +descr_floordiv, descr_rfloordiv = _make_descr_binop(_floordiv, _int_floordiv) _div = func_with_new_name(_floordiv, '_div') -descr_div, descr_rdiv = _make_descr_binop(_div) +_int_div = func_with_new_name(_int_floordiv, '_int_div') +descr_div, descr_rdiv = _make_descr_binop(_div, _int_div) def _mod(self, space, w_other): try: @@ -527,7 +528,16 @@ raise oefmt(space.w_ZeroDivisionError, "long division or modulo by zero") return space.newtuple([newlong(space, div), newlong(space, mod)]) -descr_divmod, descr_rdivmod = _make_descr_binop(_divmod) + +def _int_divmod(self, space, w_other): +try: +div, mod = self.num.int_divmod(w_other) +except ZeroDivisionError: +raise oefmt(space.w_ZeroDivisionError, +"long division or modulo by zero") +return space.newtuple([newlong(space, div), newlong(space, mod)]) + +descr_divmod, descr_rdivmod = _make_descr_binop(_divmod, _int_divmod) def newlong(space, bigint): diff --git a/pypy/objspace/std/test/test_longobject.py b/pypy/objspace/std/test/test_longobject.py --- a/pypy/objspace/std/test/test_longobject.py +++ b/pypy/objspace/std/test/test_longobject.py @@ -70,6 +70,17 @@ a = x // 1000L assert a == 3L +def test_int_floordiv(self): +x = 3000L +a = x // 1000 +assert a == 3L + +x = 3000L +a = x // -1000 +assert a == -3L + + + def test_numerator_denominator(self): assert (1L).numerator == 1L assert (1L).denominator == 1L @@ -208,6 +219,11 @@ check_division(x, y) raises(ZeroDivisionError, "x // 0L") +def test_int_divmod(self): +q, r = divmod(100L, 11) +assert q == 9L +assert r == 1L + def test_format(self): assert repr(12345678901234567890) == '12345678901234567890L' assert str(12345678901234567890) == '12345678901234567890' @@ -386,3 +402,4 @@ n = "a" * size expected = (2 << (size * 4)) // 3 assert long(n, 16) == expected + diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -781,7 +781,34 @@ def div(self, other): return self.floordiv(other) - + +@jit.elidable +def int_floordiv(self, b): +if not int_in_valid_range(b): +# Fallback to long. +return self.mul(rbigint.fromint(b)) + +digit = abs(b) +assert digit > 0 + +if self.sign == 1 and b > 0: +if digit == 1: +return self +"""elif digit & (digit - 1) == 0: +return self.rshift(ptwotable[digit]) +""" +div, mod = _divrem1(self, digit) + +if mod != 0 and self.sign * (-1 if b < 0 else 1) == -1: +if div.sign == 0: +return ONENEGATIVERBIGINT +div = div.int_add(1) +div.sign = self.sign * (-1 if b < 0 else 1) +return div + +def int_div(self, other): +return self.int_floordiv(other) + @jit.elidable def mod(self, other): if self.sign == 0: @@ -888,6 +915,30 @@ return div, mod @jit.elidable +def int_divmod(v, w): +""" Divmod with int """ + +if w == 0: +raise ZeroDivisionError("long division or modulo by zero") + +wsign = (-1 if w < 0 else 1) +if not int_in_valid_range(w) or v.sign != wsign: +# Divrem1 doesn't deal with the sign difference. Instead of having yet another copy, +# Just fallback. +return v.divmod(rbigint.fromint(w)) + +digit = abs(w) +assert digit > 0
[pypy-commit] pypy math-improvements: Test + fix for bugs found by Armin Rigo
Author: stian Branch: math-improvements Changeset: r92792:06129c0b5e0e Date: 2017-10-18 22:13 +0200 http://bitbucket.org/pypy/pypy/changeset/06129c0b5e0e/ Log:Test + fix for bugs found by Armin Rigo diff --git a/pypy/objspace/std/test/test_longobject.py b/pypy/objspace/std/test/test_longobject.py --- a/pypy/objspace/std/test/test_longobject.py +++ b/pypy/objspace/std/test/test_longobject.py @@ -2,7 +2,6 @@ from pypy.objspace.std import longobject as lobj from rpython.rlib.rbigint import rbigint - class TestW_LongObject: def test_bigint_w(self): space = self.space @@ -70,6 +69,23 @@ a = x // 1000L assert a == 3L +def test_int_floordiv(self): +import sys + +x = 3000L +a = x // 1000 +assert a == 3L + +x = 3000L +a = x // -1000 +assert a == -3L + +x = 3000L +raises(ZeroDivisionError, "x // 0") + +n = sys.maxint+1 +assert n / int(-n) == -1L + def test_numerator_denominator(self): assert (1L).numerator == 1L assert (1L).denominator == 1L @@ -208,6 +224,11 @@ check_division(x, y) raises(ZeroDivisionError, "x // 0L") +def test_int_divmod(self): +q, r = divmod(100L, 11) +assert q == 9L +assert r == 1L + def test_format(self): assert repr(12345678901234567890) == '12345678901234567890L' assert str(12345678901234567890) == '12345678901234567890' @@ -386,3 +407,4 @@ n = "a" * size expected = (2 << (size * 4)) // 3 assert long(n, 16) == expected + diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -145,6 +145,7 @@ make_sure_not_resized(digits) self._digits = digits assert size >= 0 + self.size = size or len(digits) self.sign = sign @@ -183,7 +184,9 @@ setdigit._always_inline_ = True def numdigits(self): -return self.size +w = self.size +assert w > 0 +return w numdigits._always_inline_ = True @staticmethod @@ -510,7 +513,6 @@ @jit.elidable def int_eq(self, other): """ eq with int """ - if not int_in_valid_range(other): # Fallback to Long. return self.eq(rbigint.fromint(other)) @@ -657,7 +659,7 @@ if other.sign == 0: return self elif self.sign == 0: -return rbigint(other._digits[:other.size], -other.sign, other.size) +return rbigint(other._digits[:other.numdigits()], -other.sign, other.numdigits()) elif self.sign == other.sign: result = _x_sub(self, other) else: @@ -698,7 +700,7 @@ if a._digits[0] == NULLDIGIT: return NULLRBIGINT elif a._digits[0] == ONEDIGIT: -return rbigint(b._digits[:b.size], a.sign * b.sign, b.size) +return rbigint(b._digits[:b.numdigits()], a.sign * b.sign, b.numdigits()) elif bsize == 1: res = b.widedigit(0) * a.widedigit(0) carry = res >> SHIFT @@ -740,7 +742,7 @@ bsign = -1 if b < 0 else 1 if digit == 1: -return rbigint(self._digits[:self.size], self.sign * bsign, asize) +return rbigint(self._digits[:self.numdigits()], self.sign * bsign, asize) elif asize == 1: res = self.widedigit(0) * digit carry = res >> SHIFT @@ -767,7 +769,7 @@ if self.sign == 1 and other.numdigits() == 1 and other.sign == 1: digit = other.digit(0) if digit == 1: -return rbigint(self._digits[:self.size], 1, self.size) +return rbigint(self._digits[:self.numdigits()], 1, self.numdigits()) elif digit and digit & (digit - 1) == 0: return self.rshift(ptwotable[digit]) @@ -781,7 +783,37 @@ def div(self, other): return self.floordiv(other) - + +@jit.elidable +def int_floordiv(self, b): +if not int_in_valid_range(b): +# Fallback to long. +return self.floordiv(rbigint.fromint(b)) + +if b == 0: +raise ZeroDivisionError("long division by zero") + +digit = abs(b) +assert digit > 0 + +if self.sign == 1 and b > 0: +if digit == 1: +return self +elif digit & (digit - 1) == 0: +return self.rshift(ptwotable[digit]) + +div, mod = _divrem1(self, digit) + +if mod != 0 and self.sign * (-1 if b < 0 else 1) == -1: +if div.sign == 0: +return ONENEGATIVERBIGINT +div = div.int_add(1) +
[pypy-commit] pypy math-improvements: Use long with int when overflowing
Author: stian Branch: math-improvements Changeset: r92794:c1d74e03b736 Date: 2017-10-18 22:15 +0200 http://bitbucket.org/pypy/pypy/changeset/c1d74e03b736/ Log:Use long with int when overflowing diff --git a/pypy/objspace/std/intobject.py b/pypy/objspace/std/intobject.py --- a/pypy/objspace/std/intobject.py +++ b/pypy/objspace/std/intobject.py @@ -287,7 +287,7 @@ op = getattr(operator, opname, None) assert op or ovf2small -def ovf2long(space, x, y): +def ovf2long(space, x, y, y_obj): """Handle overflowing to smalllong or long""" if _recover_with_smalllong(space): if ovf2small: @@ -298,11 +298,12 @@ a = r_longlong(x) b = r_longlong(y) return W_SmallLongObject(op(a, b)) - + from pypy.objspace.std.longobject import W_LongObject w_x = W_LongObject.fromint(space, x) -w_y = W_LongObject.fromint(space, y) -return getattr(w_x, 'descr_' + opname)(space, w_y) +#w_y = W_LongObject.fromint(space, y) + +return getattr(w_x, 'descr_' + opname)(space, y_obj) return ovf2long @@ -521,7 +522,7 @@ try: z = ovfcheck(op(x, y)) except OverflowError: -return ovf2long(space, x, y) +return ovf2long(space, x, y, w_other) else: z = op(x, y) return wrapint(space, z) @@ -543,7 +544,7 @@ try: z = ovfcheck(op(y, x)) except OverflowError: -return ovf2long(space, y, x) +return ovf2long(space, y, x, w_other) else: z = op(y, x) return wrapint(space, z) @@ -574,7 +575,7 @@ try: return func(space, x, y) except OverflowError: -return ovf2long(space, x, y) +return ovf2long(space, x, y, w_other) else: return func(space, x, y) @@ -589,7 +590,7 @@ try: return func(space, y, x) except OverflowError: -return ovf2long(space, y, x) +return ovf2long(space, y, x, w_other) else: return func(space, y, x) ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Add rlib test
Author: stian Branch: math-improvements Changeset: r92795:3a37e2483546 Date: 2017-10-18 22:57 +0200 http://bitbucket.org/pypy/pypy/changeset/3a37e2483546/ Log:Add rlib test 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 @@ -64,6 +64,29 @@ r2 = op1 // op2 assert r1.tolong() == r2 +def test_int_floordiv(self): +x = 1000L +r = rbigint.fromlong(x) +r2 = r.int_floordiv(10) +assert r2.tolong() == 100L + +assert py.test.raises(ZeroDivisionError, r.int_floordiv, 0) + +# Error pointed out by Armin Rigo +n = sys.maxint+1 +r = rbigint.fromlong(n) +assert r.int_floordiv(int(-n)).tolong() == -1L + +for x in (1, 1000, sys.maxint): +r = rbigint.fromlong(x) +rn = rbigint.fromlong(-x) +res = r.int_floordiv(x) +res2 = r.int_floordiv(-x) +res3 = rn.int_floordiv(x) +assert res.tolong() == 1L +assert res2.tolong() == -1L +assert res3.tolong() == -1L + def test_truediv(self): for op1 in gen_signs(long_vals_not_too_big): for op2 in gen_signs(long_vals): ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Missing from earlier
Author: stian Branch: math-improvements Changeset: r92793:b4e5817c17d8 Date: 2017-10-18 22:14 +0200 http://bitbucket.org/pypy/pypy/changeset/b4e5817c17d8/ Log:Missing from earlier diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py --- a/pypy/objspace/std/longobject.py +++ b/pypy/objspace/std/longobject.py @@ -491,17 +491,18 @@ "long division or modulo by zero") return newlong(space, z) -def _floordiv(self, space, w_other): +def _int_floordiv(self, space, w_other): try: -z = self.num.floordiv(w_other.asbigint()) +z = self.num.int_floordiv(w_other) except ZeroDivisionError: raise oefmt(space.w_ZeroDivisionError, "long division or modulo by zero") return newlong(space, z) -descr_floordiv, descr_rfloordiv = _make_descr_binop(_floordiv) +descr_floordiv, descr_rfloordiv = _make_descr_binop(_floordiv, _int_floordiv) _div = func_with_new_name(_floordiv, '_div') -descr_div, descr_rdiv = _make_descr_binop(_div) +_int_div = func_with_new_name(_int_floordiv, '_int_div') +descr_div, descr_rdiv = _make_descr_binop(_div, _int_div) def _mod(self, space, w_other): try: @@ -527,7 +528,16 @@ raise oefmt(space.w_ZeroDivisionError, "long division or modulo by zero") return space.newtuple([newlong(space, div), newlong(space, mod)]) -descr_divmod, descr_rdivmod = _make_descr_binop(_divmod) + +def _int_divmod(self, space, w_other): +try: +div, mod = self.num.int_divmod(w_other) +except ZeroDivisionError: +raise oefmt(space.w_ZeroDivisionError, +"long division or modulo by zero") +return space.newtuple([newlong(space, div), newlong(space, mod)]) + +descr_divmod, descr_rdivmod = _make_descr_binop(_divmod, _int_divmod) def newlong(space, bigint): ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: branch with some rbigint/longobject/intobject improvements
Author: stian Branch: math-improvements Changeset: r92791:ec9abaebdc28 Date: 2017-10-18 22:10 +0200 http://bitbucket.org/pypy/pypy/changeset/ec9abaebdc28/ Log:branch with some rbigint/longobject/intobject improvements ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Make use of int_pow
Author: stian Branch: math-improvements Changeset: r92796:ab5af3aa60e3 Date: 2017-10-18 23:16 +0200 http://bitbucket.org/pypy/pypy/changeset/ab5af3aa60e3/ Log:Make use of int_pow diff --git a/pypy/objspace/std/intobject.py b/pypy/objspace/std/intobject.py --- a/pypy/objspace/std/intobject.py +++ b/pypy/objspace/std/intobject.py @@ -268,7 +268,7 @@ return ix -def _pow_ovf2long(space, iv, iw, w_modulus): +def _pow_ovf2long(space, iv, iw, iw_obj, w_modulus): if space.is_none(w_modulus) and _recover_with_smalllong(space): from pypy.objspace.std.smalllongobject import _pow as _pow_small try: @@ -279,8 +279,8 @@ pass from pypy.objspace.std.longobject import W_LongObject w_iv = W_LongObject.fromint(space, iv) -w_iw = W_LongObject.fromint(space, iw) -return w_iv.descr_pow(space, w_iw, w_modulus) + +return w_iv.descr_pow(space, iw_obj, w_modulus) def _make_ovf2long(opname, ovf2small=None): @@ -292,17 +292,16 @@ if _recover_with_smalllong(space): if ovf2small: return ovf2small(space, x, y) -# Assume a generic operation without an explicit ovf2small +# Assume a generic operation without an explicit #iovf2small # handler from pypy.objspace.std.smalllongobject import W_SmallLongObject a = r_longlong(x) b = r_longlong(y) return W_SmallLongObject(op(a, b)) - + from pypy.objspace.std.longobject import W_LongObject w_x = W_LongObject.fromint(space, x) -#w_y = W_LongObject.fromint(space, y) - + return getattr(w_x, 'descr_' + opname)(space, y_obj) return ovf2long @@ -472,12 +471,12 @@ # can't return NotImplemented (space.pow doesn't do full # ternary, i.e. w_modulus.__zpow__(self, w_exponent)), so # handle it ourselves -return _pow_ovf2long(space, x, y, w_modulus) +return _pow_ovf2long(space, x, y, w_exponent, w_modulus) try: result = _pow(space, x, y, z) except (OverflowError, ValueError): -return _pow_ovf2long(space, x, y, w_modulus) +return _pow_ovf2long(space, x, y, w_exponent, w_modulus) return space.newint(result) @unwrap_spec(w_modulus=WrappedDefault(None)) ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Cleanup functio
Author: stian Branch: math-improvements Changeset: r92798:114b6da85abb Date: 2017-10-19 12:05 +0200 http://bitbucket.org/pypy/pypy/changeset/114b6da85abb/ Log:Cleanup functio diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -931,16 +931,12 @@ # Just fallback. return v.divmod(rbigint.fromint(w)) - digit = abs(w) assert digit > 0 div, mod = _divrem1(v, digit) - div.sign = v.sign * wsign - - if v.sign != wsign: if div.sign == 0: div = NEGATIVERBIGINT ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Fix build issues
Author: stian Branch: math-improvements Changeset: r92799:4e50c695d26e Date: 2017-10-19 12:27 +0200 http://bitbucket.org/pypy/pypy/changeset/4e50c695d26e/ Log:Fix build issues diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py --- a/pypy/objspace/std/longobject.py +++ b/pypy/objspace/std/longobject.py @@ -308,10 +308,12 @@ @unwrap_spec(w_modulus=WrappedDefault(None)) def descr_pow(self, space, w_exponent, w_modulus=None): +exp_int = 0 +exp_bigint = None +sign = 0 + if isinstance(w_exponent, W_AbstractIntObject): exp_int = w_exponent.int_w(space) -sign = 0 -use_int = True if exp_int > 0: sign = 1 elif exp_int < 0: @@ -321,14 +323,13 @@ else: exp_bigint = w_exponent.asbigint() sign = exp_bigint.sign -use_int = False if space.is_none(w_modulus): if sign < 0: self = self.descr_float(space) w_exponent = w_exponent.descr_float(space) return space.pow(self, w_exponent, space.w_None) -if use_int: +if not exp_bigint: return W_LongObject(self.num.int_pow(exp_int)) else: return W_LongObject(self.num.pow(exp_bigint)) @@ -344,7 +345,7 @@ "pow() 2nd argument cannot be negative when 3rd " "argument specified") try: -if use_int: +if not exp_bigint: result = self.num.int_pow(exp_int, w_modulus.asbigint()) else: result = self.num.pow(exp_bigint, w_modulus.asbigint()) diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -939,7 +939,7 @@ if v.sign != wsign: if div.sign == 0: -div = NEGATIVERBIGINT +div = ONENEGATIVERBIGINT else: div = div.int_sub(1) mod = w - mod ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Add one more case to divmod, add tests to int_divmod, add int_pow tests.
Author: stian Branch: math-improvements Changeset: r92797:6eedf6a4b154 Date: 2017-10-19 12:04 +0200 http://bitbucket.org/pypy/pypy/changeset/6eedf6a4b154/ Log:Add one more case to divmod, add tests to int_divmod, add int_pow tests. diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py --- a/pypy/objspace/std/longobject.py +++ b/pypy/objspace/std/longobject.py @@ -309,27 +309,45 @@ @unwrap_spec(w_modulus=WrappedDefault(None)) def descr_pow(self, space, w_exponent, w_modulus=None): if isinstance(w_exponent, W_AbstractIntObject): -w_exponent = w_exponent.descr_long(space) +exp_int = w_exponent.int_w(space) +sign = 0 +use_int = True +if exp_int > 0: +sign = 1 +elif exp_int < 0: +sign = -1 elif not isinstance(w_exponent, W_AbstractLongObject): return space.w_NotImplemented - +else: +exp_bigint = w_exponent.asbigint() +sign = exp_bigint.sign +use_int = False + if space.is_none(w_modulus): -if w_exponent.asbigint().sign < 0: +if sign < 0: self = self.descr_float(space) w_exponent = w_exponent.descr_float(space) return space.pow(self, w_exponent, space.w_None) -return W_LongObject(self.num.pow(w_exponent.asbigint())) +if use_int: +return W_LongObject(self.num.int_pow(exp_int)) +else: +return W_LongObject(self.num.pow(exp_bigint)) + elif isinstance(w_modulus, W_AbstractIntObject): w_modulus = w_modulus.descr_long(space) + elif not isinstance(w_modulus, W_AbstractLongObject): return space.w_NotImplemented -if w_exponent.asbigint().sign < 0: +if sign < 0: raise oefmt(space.w_TypeError, "pow() 2nd argument cannot be negative when 3rd " "argument specified") try: -result = self.num.pow(w_exponent.asbigint(), w_modulus.asbigint()) +if use_int: +result = self.num.int_pow(exp_int, w_modulus.asbigint()) +else: +result = self.num.pow(exp_bigint, w_modulus.asbigint()) except ValueError: raise oefmt(space.w_ValueError, "pow 3rd argument cannot be 0") return W_LongObject(result) diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -927,20 +927,29 @@ raise ZeroDivisionError("long division or modulo by zero") wsign = (-1 if w < 0 else 1) -if not int_in_valid_range(w) or v.sign != wsign: -# Divrem1 doesn't deal with the sign difference. Instead of having yet another copy, +if not int_in_valid_range(w) or (wsign == -1 and v.sign != wsign): # Just fallback. return v.divmod(rbigint.fromint(w)) - + + digit = abs(w) assert digit > 0 div, mod = _divrem1(v, digit) -mod = rbigint.fromint(mod * wsign) + +div.sign = v.sign * wsign + -#mod.sign = wsign -div.sign = v.sign * wsign - + +if v.sign != wsign: +if div.sign == 0: +div = NEGATIVERBIGINT +else: +div = div.int_sub(1) +mod = w - mod + +mod = rbigint.fromint(wsign * mod) + return div, mod @jit.elidable @@ -994,9 +1003,7 @@ elif a.sign == 0: return NULLRBIGINT elif size_b == 1: -if b._digits[0] == NULLDIGIT: -return ONERBIGINT if a.sign == 1 else ONENEGATIVERBIGINT -elif b._digits[0] == ONEDIGIT: +if b._digits[0] == ONEDIGIT: return a elif a.numdigits() == 1: adigit = a.digit(0) @@ -1084,6 +1091,89 @@ return z @jit.elidable +def int_pow(a, b, c=None): +negativeOutput = False # if x<0 return negative output + +# 5-ary values. If the exponent is large enough, table is +# precomputed so that table[i] == a**i % c for i in range(32). +# python translation: the table is computed when needed. + +if b < 0: # if exponent is negative +if c is not None: +raise TypeError( +"pow() 2nd argument " +"cannot be negative when 3rd argument specified") +# XXX failed to implement +raise ValueError("bigint pow() too negative") + +if c is not None: +if c.sign
[pypy-commit] pypy math-improvements: Make use of int_sub in longobjects
Author: stian Branch: math-improvements Changeset: r92803:62ba73fa6cac Date: 2017-10-19 22:47 +0200 http://bitbucket.org/pypy/pypy/changeset/62ba73fa6cac/ Log:Make use of int_sub in longobjects diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py --- a/pypy/objspace/std/longobject.py +++ b/pypy/objspace/std/longobject.py @@ -395,10 +395,14 @@ methname = opname + '_' if opname in ('and', 'or') else opname descr_rname = 'descr_r' + opname op = getattr(rbigint, methname) +intop = getattr(rbigint, 'int_' + methname) @func_renamer('descr_' + opname) -@delegate_other def descr_binop(self, space, w_other): +if isinstance(w_other, W_AbstractIntObject): +return W_LongObject(intop(self.num, w_other.int_w(space))) +elif not isinstance(w_other, W_AbstractLongObject): +return space.w_NotImplemented return W_LongObject(op(self.num, w_other.asbigint())) @func_renamer(descr_rname) ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Ups, not suppose to include this code
Author: stian Branch: math-improvements Changeset: r92806:6e8fd621566a Date: 2017-10-20 01:17 +0200 http://bitbucket.org/pypy/pypy/changeset/6e8fd621566a/ Log:Ups, not suppose to include this code diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -748,8 +748,6 @@ return rbigint(self._digits[:asize], self.sign * bsign, asize) elif digit & (digit - 1) == 0: result = self.lqshift(ptwotable[digit]) -elif digit == 10: -result = self.lqshift(3).add(self.lqshift(1)) elif asize == 1: res = self.widedigit(0) * digit carry = res >> SHIFT ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Prebuild nulldigits list for use on null results where the list is not modified, reorder if operations in int_mul so power of two happens before single size check
Author: stian Branch: math-improvements Changeset: r92805:587f1f780bd1 Date: 2017-10-19 23:43 +0200 http://bitbucket.org/pypy/pypy/changeset/587f1f780bd1/ Log:Prebuild nulldigits list for use on null results where the list is not modified, reorder if operations in int_mul so power of two happens before single size check diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -108,6 +108,7 @@ NULLDIGIT = _store_digit(0) ONEDIGIT = _store_digit(1) +NULLDIGITS = [NULLDIGIT] def _check_digits(l): for x in l: @@ -139,7 +140,7 @@ _immutable_ = True _immutable_fields_ = ["_digits"] -def __init__(self, digits=[NULLDIGIT], sign=0, size=0): +def __init__(self, digits=NULLDIGITS, sign=0, size=0): if not we_are_translated(): _check_digits(digits) make_sure_not_resized(digits) @@ -742,9 +743,13 @@ bsign = -1 if b < 0 else 1 if digit == 1: -if self.sign == bsign: +if bsign == 1: return self -return rbigint(self._digits[:self.numdigits()], self.sign * bsign, asize) +return rbigint(self._digits[:asize], self.sign * bsign, asize) +elif digit & (digit - 1) == 0: +result = self.lqshift(ptwotable[digit]) +elif digit == 10: +result = self.lqshift(3).add(self.lqshift(1)) elif asize == 1: res = self.widedigit(0) * digit carry = res >> SHIFT @@ -752,9 +757,6 @@ return rbigint([_store_digit(res & MASK), _store_digit(carry)], self.sign * bsign, 2) else: return rbigint([_store_digit(res & MASK)], self.sign * bsign, 1) - -elif digit & (digit - 1) == 0: -result = self.lqshift(ptwotable[digit]) else: result = _muladd1(self, digit) @@ -1395,7 +1397,7 @@ self.size = i if self.numdigits() == 1 and self._digits[0] == NULLDIGIT: self.sign = 0 -self._digits = [NULLDIGIT] +self._digits = NULLDIGITS _normalize._always_inline_ = True @@ -1486,7 +1488,7 @@ if x > 0: return digits_from_nonneg_long(x), 1 elif x == 0: -return [NULLDIGIT], 0 +return NULLDIGITS, 0 elif x != most_neg_value_of_same_type(x): # normal case return digits_from_nonneg_long(-x), -1 @@ -1504,7 +1506,7 @@ def args_from_long(x): if x >= 0: if x == 0: -return [NULLDIGIT], 0 +return NULLDIGITS, 0 else: return digits_from_nonneg_long(x), 1 else: @@ -1766,8 +1768,8 @@ size_lo = min(size_n, size) # We use "or" her to avoid having a check where list can be empty in _normalize. -lo = rbigint(n._digits[:size_lo] or [NULLDIGIT], 1) -hi = rbigint(n._digits[size_lo:n.size] or [NULLDIGIT], 1) +lo = rbigint(n._digits[:size_lo] or NULLDIGITS, 1) +hi = rbigint(n._digits[size_lo:n.size] or NULLDIGITS, 1) lo._normalize() hi._normalize() return hi, lo 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 @@ -28,8 +28,8 @@ class TestRLong(object): def test_simple(self): -for op1 in [-2, -1, 0, 1, 2, 50]: -for op2 in [-2, -1, 0, 1, 2, 50]: +for op1 in [-2, -1, 0, 1, 2, 10, 50]: +for op2 in [-2, -1, 0, 1, 2, 10, 50]: rl_op1 = rbigint.fromint(op1) rl_op2 = rbigint.fromint(op2) for op in "add sub mul".split(): ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Avoid copy if the sign stay the same in int_mul
Author: stian Branch: math-improvements Changeset: r92804:0f49fdf5b940 Date: 2017-10-19 23:03 +0200 http://bitbucket.org/pypy/pypy/changeset/0f49fdf5b940/ Log:Avoid copy if the sign stay the same in int_mul diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -742,6 +742,8 @@ bsign = -1 if b < 0 else 1 if digit == 1: +if self.sign == bsign: +return self return rbigint(self._digits[:self.numdigits()], self.sign * bsign, asize) elif asize == 1: res = self.widedigit(0) * digit ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Undo this move, it is actully 50% slower for power of two calculations on single digit longs
Author: stian Branch: math-improvements Changeset: r92807:bbeb35d80f5f Date: 2017-10-20 02:05 +0200 http://bitbucket.org/pypy/pypy/changeset/bbeb35d80f5f/ Log:Undo this move, it is actully 50% slower for power of two calculations on single digit longs diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -746,8 +746,6 @@ if bsign == 1: return self return rbigint(self._digits[:asize], self.sign * bsign, asize) -elif digit & (digit - 1) == 0: -result = self.lqshift(ptwotable[digit]) elif asize == 1: res = self.widedigit(0) * digit carry = res >> SHIFT @@ -755,6 +753,8 @@ return rbigint([_store_digit(res & MASK), _store_digit(carry)], self.sign * bsign, 2) else: return rbigint([_store_digit(res & MASK)], self.sign * bsign, 1) +elif digit & (digit - 1) == 0: +result = self.lqshift(ptwotable[digit]) else: result = _muladd1(self, digit) ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Add uint128_t, and use it to speed up mul and lshift slightly. TODO: Tests missing.
Author: stian Branch: math-improvements Changeset: r92810:e4fc38341ad9 Date: 2017-10-21 05:56 +0200 http://bitbucket.org/pypy/pypy/changeset/e4fc38341ad9/ Log:Add uint128_t, and use it to speed up mul and lshift slightly. TODO: Tests missing. diff --git a/pypy/objspace/std/longobject.py b/pypy/objspace/std/longobject.py --- a/pypy/objspace/std/longobject.py +++ b/pypy/objspace/std/longobject.py @@ -460,11 +460,9 @@ return space.w_NotImplemented return func(self, space, w_other) else: -@delegate_other @func_renamer('descr_' + opname) def descr_binop(self, space, w_other): return func(self, space, w_other) -@delegate_other @func_renamer('descr_r' + opname) def descr_rbinop(self, space, w_other): if not isinstance(w_other, W_LongObject): diff --git a/rpython/rlib/rarithmetic.py b/rpython/rlib/rarithmetic.py --- a/rpython/rlib/rarithmetic.py +++ b/rpython/rlib/rarithmetic.py @@ -614,6 +614,7 @@ r_ulonglong = build_int('r_ulonglong', False, 64) r_longlonglong = build_int('r_longlonglong', True, 128) +r_ulonglonglong = build_int('r_ulonglonglong', False, 128) longlongmax = r_longlong(LONGLONG_TEST - 1) if r_longlong is not r_int: diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -27,6 +27,7 @@ else: UDIGIT_MASK = longlongmask LONG_TYPE = rffi.__INT128_T +ULONG_TYPE = rffi.__UINT128_T if LONG_BIT > SHIFT: STORE_TYPE = lltype.Signed UNSIGNED_TYPE = lltype.Unsigned @@ -40,7 +41,8 @@ STORE_TYPE = lltype.Signed UNSIGNED_TYPE = lltype.Unsigned LONG_TYPE = rffi.LONGLONG - +ULONG_TYPE = rffi.ULONGLONG + MASK = int((1 << SHIFT) - 1) FLOAT_MULTIPLIER = float(1 << SHIFT) @@ -97,6 +99,9 @@ def _widen_digit(x): return rffi.cast(LONG_TYPE, x) +def _unsigned_widen_digit(x): +return rffi.cast(ULONG_TYPE, x) + @specialize.argtype(0) def _store_digit(x): return rffi.cast(STORE_TYPE, x) @@ -139,15 +144,16 @@ """This is a reimplementation of longs using a list of digits.""" _immutable_ = True _immutable_fields_ = ["_digits"] - + def __init__(self, digits=NULLDIGITS, sign=0, size=0): if not we_are_translated(): _check_digits(digits) make_sure_not_resized(digits) self._digits = digits + assert size >= 0 +self.size = size or len(digits) -self.size = size or len(digits) self.sign = sign # __eq__ and __ne__ method exist for testingl only, they are not RPython! @@ -172,6 +178,12 @@ return _widen_digit(self._digits[x]) widedigit._always_inline_ = True +def uwidedigit(self, x): +"""Return the x'th digit, as a long long int if needed +to have enough room to contain two digits.""" +return _unsigned_widen_digit(self._digits[x]) +uwidedigit._always_inline_ = True + def udigit(self, x): """Return the x'th digit, as an unsigned int.""" return _load_unsigned_digit(self._digits[x]) @@ -701,9 +713,9 @@ if a._digits[0] == NULLDIGIT: return NULLRBIGINT elif a._digits[0] == ONEDIGIT: -return rbigint(b._digits[:b.numdigits()], a.sign * b.sign, b.numdigits()) +return rbigint(b._digits[:bsize], a.sign * b.sign, bsize) elif bsize == 1: -res = b.widedigit(0) * a.widedigit(0) +res = b.uwidedigit(0) * a.uwidedigit(0) carry = res >> SHIFT if carry: return rbigint([_store_digit(res & MASK), _store_digit(carry)], a.sign * b.sign, 2) @@ -740,6 +752,7 @@ asize = self.numdigits() digit = abs(b) + bsign = -1 if b < 0 else 1 if digit == 1: @@ -747,7 +760,8 @@ return self return rbigint(self._digits[:asize], self.sign * bsign, asize) elif asize == 1: -res = self.widedigit(0) * digit +udigit = r_uint(digit) +res = self.uwidedigit(0) * udigit carry = res >> SHIFT if carry: return rbigint([_store_digit(res & MASK), _store_digit(carry)], self.sign * bsign, 2) @@ -839,7 +853,7 @@ rem = self.widedigit(size) size -= 1 while size >= 0: -rem = ((rem << SHIFT) + self.widedigit(size)) % digit +rem = ((rem << SHIFT) | self.digit(size)) % digit s
[pypy-commit] pypy math-improvements: Digits don't change post-construction
Author: stian Branch: math-improvements Changeset: r92839:7427553eee6b Date: 2017-10-24 18:42 +0200 http://bitbucket.org/pypy/pypy/changeset/7427553eee6b/ Log:Digits don't change post-construction diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -143,7 +143,7 @@ class rbigint(object): """This is a reimplementation of longs using a list of digits.""" _immutable_ = True -_immutable_fields_ = ["_digits", "size", "sign"] +_immutable_fields_ = ["_digits[*]", "size", "sign"] def __init__(self, digits=NULLDIGITS, sign=0, size=0): if not we_are_translated(): ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: replace construction of a onedigit with premade, and mark sign and size as immutable (which is true post contruction)
Author: stian Branch: math-improvements Changeset: r92838:2a90db93be84 Date: 2017-10-24 15:03 +0200 http://bitbucket.org/pypy/pypy/changeset/2a90db93be84/ Log:replace construction of a onedigit with premade, and mark sign and size as immutable (which is true post contruction) diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -143,7 +143,7 @@ class rbigint(object): """This is a reimplementation of longs using a list of digits.""" _immutable_ = True -_immutable_fields_ = ["_digits"] +_immutable_fields_ = ["_digits", "size", "sign"] def __init__(self, digits=NULLDIGITS, sign=0, size=0): if not we_are_translated(): @@ -1033,7 +1033,7 @@ # At this point a, b, and c are guaranteed non-negative UNLESS # c is NULL, in which case a may be negative. */ -z = rbigint([ONEDIGIT], 1, 1) +z = ONERBIGINT # python adaptation: moved macros REDUCE(X) and MULT(X, Y, result) # into helper function result = _help_mult(x, y, c) @@ -1168,7 +1168,7 @@ # At this point a, b, and c are guaranteed non-negative UNLESS # c is NULL, in which case a may be negative. */ -z = rbigint([ONEDIGIT], 1, 1) +z = ONERBIGINT # python adaptation: moved macros REDUCE(X) and MULT(X, Y, result) # into helper function result = _help_mult(x, y, c) ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Fix int_mod with mod argument
Author: stian Branch: math-improvements Changeset: r92840:e80b5cdab0a6 Date: 2017-10-24 21:38 +0200 http://bitbucket.org/pypy/pypy/changeset/e80b5cdab0a6/ Log:Fix int_mod with mod argument diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -982,7 +982,9 @@ size_b = b.numdigits() -if c is not None: +if b.sign == 0: +return ONERBIGINT +elif c is not None: if c.sign == 0: raise ValueError("pow() 3rd argument cannot be 0") @@ -1009,15 +1011,12 @@ # so we only do it when it buys something. if a.sign < 0 or a.numdigits() > c.numdigits(): a = a.mod(c) - -elif b.sign == 0: -return ONERBIGINT elif a.sign == 0: return NULLRBIGINT elif size_b == 1: if b._digits[0] == ONEDIGIT: return a -elif a.numdigits() == 1: +elif a.numdigits() == 1 and c is None: adigit = a.digit(0) digit = b.digit(0) if adigit == 1: @@ -1118,7 +1117,10 @@ # XXX failed to implement raise ValueError("bigint pow() too negative") -if c is not None: +assert b >= 0 +if b == 0: +return ONERBIGINT +elif c is not None: if c.sign == 0: raise ValueError("pow() 3rd argument cannot be 0") @@ -1145,13 +1147,9 @@ # so we only do it when it buys something. if a.sign < 0 or a.numdigits() > c.numdigits(): a = a.mod(c) - -elif b == 0: -return ONERBIGINT elif a.sign == 0: return NULLRBIGINT - -if b == 1: +elif b == 1: return a elif a.numdigits() == 1: adigit = a.digit(0) @@ -1175,6 +1173,7 @@ # Left-to-right binary exponentiation (HAC Algorithm 14.79) # http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf j = 1 << (SHIFT-1) + while j != 0: z = _help_mult(z, z, c) if b & j: 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 @@ -164,6 +164,11 @@ r2 = op1 ** op2 assert r1.tolong() == r2 +r3 = rl_op1.int_pow(op2, rbigint.fromint(1000)) +r4 = pow(op1, op2, 1000) +print op1, op2 +assert r3.tolong() == r4 + def test_int_pow(self): for op1 in gen_signs(long_vals_not_too_big[:-2]): for op2 in [0, 1, 2, 8, 9, 10, 11]: @@ -171,6 +176,12 @@ r1 = rl_op1.int_pow(op2) r2 = op1 ** op2 assert r1.tolong() == r2 + +r3 = rl_op1.int_pow(op2, rbigint.fromint(1000)) +r4 = pow(op1, op2, 1000) +print op1, op2 +assert r3.tolong() == r4 + def test_touint(self): result = r_uint(sys.maxint + 42) rl = rbigint.fromint(sys.maxint).add(rbigint.fromint(42)) ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: uint128_t test and a tiny optimalization
Author: stian Branch: math-improvements Changeset: r92854:12d7e0578291 Date: 2017-10-26 18:48 +0200 http://bitbucket.org/pypy/pypy/changeset/12d7e0578291/ Log:uint128_t test and a tiny optimalization diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -849,6 +849,7 @@ else: # Perform size = self.numdigits() - 1 + if size > 0: rem = self.widedigit(size) size -= 1 @@ -856,7 +857,7 @@ rem = ((rem << SHIFT) | self.digit(size)) % digit size -= 1 else: -rem = self.digit(0) % digit +rem = self.widedigit(0) % digit if rem == 0: return NULLRBIGINT @@ -2091,7 +2092,7 @@ * result in z[0:m], and return the d bits shifted out of the top. """ -carry = 0 +carry = _unsigned_widen_digit(0) assert 0 <= d and d < SHIFT i = 0 while i < m: diff --git a/rpython/translator/c/test/test_typed.py b/rpython/translator/c/test/test_typed.py --- a/rpython/translator/c/test/test_typed.py +++ b/rpython/translator/c/test/test_typed.py @@ -955,6 +955,20 @@ res = f(217) assert res == 305123851 +def test_uint128(self): +if not hasattr(rffi, '__UINT128_T'): +py.test.skip("no '__uint128_t'") +def func(n): +x = rffi.cast(getattr(rffi, '__UINT128_T'), n) +x *= x +x *= x +x *= x +x *= x +return intmask(x >> 96) +f = self.getcompiled(func, [int]) +res = f(217) +assert res == 305123851 + def test_bool_2(self): def func(n): x = rffi.cast(lltype.Bool, n) ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Speed up division slightly
Author: stian Branch: math-improvements Changeset: r92915:28ef9f10c404 Date: 2017-11-03 15:34 +0100 http://bitbucket.org/pypy/pypy/changeset/28ef9f10c404/ Log:Speed up division slightly diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -2168,12 +2168,13 @@ if j >= size_v: vtop = 0 else: -vtop = v.widedigit(j) -assert vtop <= wm1 -vv = (vtop << SHIFT) | v.widedigit(abs(j-1)) +vtop = v.widedigit(j) << SHIFT +#assert vtop <= wm1 +vv = vtop | v.widedigit(abs(j-1)) q = vv / wm1 -r = vv - wm1 * q -while wm2 * q > ((r << SHIFT) | v.widedigit(abs(j-2))): +r = vv % wm1 # This seems to be slightly faster than on widen digits than vv - wm1 * q. +vj2 = v.widedigit(abs(j-2)) +while wm2 * q > ((r << SHIFT) | vj2): q -= 1 r += wm1 ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Make rshift invert (in most cases) in place, this makes a huge speedup for rshift with negative numbers as it avoids two extra copies, also make an rqshift for th
Author: stian Branch: math-improvements Changeset: r92929:f30c2f38b0b5 Date: 2017-11-04 19:18 +0100 http://bitbucket.org/pypy/pypy/changeset/f30c2f38b0b5/ Log:Make rshift invert (in most cases) in place, this makes a huge speedup for rshift with negative numbers as it avoids two extra copies, also make an rqshift for the power of twos diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -787,7 +787,7 @@ if digit == 1: return rbigint(self._digits[:self.numdigits()], 1, self.numdigits()) elif digit and digit & (digit - 1) == 0: -return self.rshift(ptwotable[digit]) +return self.rqshift(ptwotable[digit]) div, mod = _divrem(self, other) if mod.sign * other.sign == -1: @@ -816,7 +816,7 @@ if digit == 1: return self elif digit & (digit - 1) == 0: -return self.rshift(ptwotable[digit]) +return self.rqshift(ptwotable[digit]) div, mod = _divrem1(self, digit) @@ -1267,31 +1267,85 @@ raise ValueError("negative shift count") elif int_other == 0: return self +invert = False if self.sign == -1 and not dont_invert: -a = self.invert().rshift(int_other) -return a.invert() +first = self.digit(0) +if first == 0: +a = self.invert().rshift(int_other) +return a.invert() +invert = True wordshift = int_other / SHIFT +loshift = int_other % SHIFT newsize = self.numdigits() - wordshift if newsize <= 0: -return NULLRBIGINT - -loshift = int_other % SHIFT +if invert: +return ONENEGATIVERBIGINT +else: +return NULLRBIGINT + + hishift = SHIFT - loshift z = rbigint([NULLDIGIT] * newsize, self.sign, newsize) i = 0 while i < newsize: -newdigit = (self.udigit(wordshift) >> loshift) +digit = self.udigit(wordshift) +if i == 0 and invert and wordshift == 0: +digit -= 1 +newdigit = (digit >> loshift) if i+1 < newsize: newdigit |= (self.udigit(wordshift+1) << hishift) z.setdigit(i, newdigit) i += 1 wordshift += 1 +if invert: +z.setdigit(0, z.digit(0)+1) z._normalize() return z rshift._always_inline_ = 'try' # It's so fast that it's always benefitial. @jit.elidable +def rqshift(self, int_other): +wordshift = int_other / SHIFT +loshift = int_other % SHIFT +newsize = self.numdigits() - wordshift + +invert = False +if self.sign == -1: +first = self.digit(0) +if first == 0: +a = self.invert().rqshift(int_other) +return a.invert() +invert = True + +if newsize <= 0: +if invert: +return ONENEGATIVERBIGINT +else: +return NULLRBIGINT + + +hishift = SHIFT - loshift +z = rbigint([NULLDIGIT] * newsize, self.sign, newsize) +i = 0 +inverted = False +while i < newsize: +digit = self.udigit(wordshift) +if invert and i == 0 and wordshift == 0: +digit -= 1 +newdigit = (digit >> loshift) +if i+1 < newsize: +newdigit |= (self.udigit(wordshift+1) << hishift) +z.setdigit(i, newdigit) +i += 1 +wordshift += 1 +if invert: +z.setdigit(0, z.digit(0)+1) +z._normalize() +return z +rshift._always_inline_ = 'try' # It's so fast that it's always benefitial. + +@jit.elidable def abs_rshift_and_mask(self, bigshiftcount, mask): assert isinstance(bigshiftcount, r_ulonglong) assert mask >= 0 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 @@ -598,6 +598,33 @@ res3 = f1.abs_rshift_and_mask(r_ulonglong(y), mask) assert res3 == (abs(x) >> y) & mask +def test_qshift(self): +for x in range(10): +for y in range(1, 161, 16): +num = (x << y) + x +f1 = rbigint.fromlong(num) +nf1 = rbigint.fromlong(-num) + +for z in range(1, 31): +res1 = f1.lqshift(z).tolong() +res2 = f
[pypy-commit] pypy math-improvements: Kill dead code, clean up normalization, and disable an assert that causes C code warnings. Its a helper function for _x_divrem and since d is SHIFT - bits_in_digi
Author: stian Branch: math-improvements Changeset: r92970:7f48dd825978 Date: 2017-11-08 03:59 +0100 http://bitbucket.org/pypy/pypy/changeset/7f48dd825978/ Log:Kill dead code, clean up normalization, and disable an assert that causes C code warnings. Its a helper function for _x_divrem and since d is SHIFT - bits_in_digit, which is always SHIFT or smaller already diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -1459,9 +1459,8 @@ i -= 1 assert i > 0 -if i != self.numdigits(): -self.size = i -if self.numdigits() == 1 and self._digits[0] == NULLDIGIT: +self.size = i +if i == 1 and self._digits[0] == NULLDIGIT: self.sign = 0 self._digits = NULLDIGITS @@ -1940,103 +1939,6 @@ ret._normalize() return ret -""" (*) Why adding t3 can't "run out of room" above. - -Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts -to start with: - -1. For any integer i, i = c(i/2) + f(i/2). In particular, - bsize = c(bsize/2) + f(bsize/2). -2. shift = f(bsize/2) -3. asize <= bsize -4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this - routine, so asize > bsize/2 >= f(bsize/2) in this routine. - -We allocated asize + bsize result digits, and add t3 into them at an offset -of shift. This leaves asize+bsize-shift allocated digit positions for t3 -to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) = -asize + c(bsize/2) available digit positions. - -bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has -at most c(bsize/2) digits + 1 bit. - -If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2) -digits, and al has at most f(bsize/2) digits in any case. So ah+al has at -most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit. - -The product (ah+al)*(bh+bl) therefore has at most - -c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits - -and we have asize + c(bsize/2) available digit positions. We need to show -this is always enough. An instance of c(bsize/2) cancels out in both, so -the question reduces to whether asize digits is enough to hold -(asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize, -then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4, -asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1 -digit is enough to hold 2 bits. This is so since SHIFT=15 >= 2. If -asize == bsize, then we're asking whether bsize digits is enough to hold -c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits -is enough to hold 2 bits. This is so if bsize >= 2, which holds because -bsize >= KARATSUBA_CUTOFF >= 2. - -Note that since there's always enough room for (ah+al)*(bh+bl), and that's -clearly >= each of ah*bh and al*bl, there's always enough room to subtract -ah*bh and al*bl too. -""" - -def _k_lopsided_mul(a, b): -# Not in use anymore, only account for like 1% performance. Perhaps if we -# Got rid of the extra list allocation this would be more effective. -""" -b has at least twice the digits of a, and a is big enough that Karatsuba -would pay off *if* the inputs had balanced sizes. View b as a sequence -of slices, each with a->ob_size digits, and multiply the slices by a, -one at a time. This gives k_mul balanced inputs to work with, and is -also cache-friendly (we compute one double-width slice of the result -at a time, then move on, never bactracking except for the helpful -single-width slice overlap between successive partial sums). -""" -asize = a.numdigits() -bsize = b.numdigits() -# nbdone is # of b digits already multiplied - -assert asize > KARATSUBA_CUTOFF -assert 2 * asize <= bsize - -# Allocate result space, and zero it out. -ret = rbigint([NULLDIGIT] * (asize + bsize), 1) - -# Successive slices of b are copied into bslice. -#bslice = rbigint([0] * asize, 1) -# XXX we cannot pre-allocate, see comments below! -# XXX prevent one list from being created. -bslice = rbigint(sign=1) - -nbdone = 0 -while bsize > 0: -nbtouse = min(bsize, asize) - -# Multiply the next slice of b by a. - -#bslice.digits[:nbtouse] = b.digits[nbdone : nbdone + nbtouse] -# XXX: this would be more efficient if we adopted CPython's -# way to store the size, instead of resizing the list! -# XXX change the implementation, encoding length via the sign. -bslice._digits = b._digits[nbdone : nbdone + nbtouse] -bslice.size = nbtouse -product = _k_mul(a, bslice) - -# Add int
[pypy-commit] pypy math-improvements: Kill test for removed function
Author: stian Branch: math-improvements Changeset: r92971:b9cf8efa4db1 Date: 2017-11-08 04:01 +0100 http://bitbucket.org/pypy/pypy/changeset/b9cf8efa4db1/ Log:Kill test for removed function 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 @@ -616,7 +616,7 @@ assert res3 == -num << z assert res4 == -num >> z -# Large digit +# Large digit, also invertion test. for x in range((1 << SHIFT) - 10, (1 << SHIFT) + 10): f1 = rbigint.fromlong(x) nf1 = rbigint.fromlong(-x) @@ -871,14 +871,6 @@ ret = lobj._k_mul(f1, f2) assert ret.tolong() == f1.tolong() * f2.tolong() -def test__k_lopsided_mul(self): -digs_a = KARATSUBA_CUTOFF + 3 -digs_b = 3 * digs_a -f1 = bigint([lobj.MASK] * digs_a, 1) -f2 = bigint([lobj.MASK] * digs_b, 1) -ret = lobj._k_lopsided_mul(f1, f2) -assert ret.tolong() == f1.tolong() * f2.tolong() - def test_longlong(self): max = 1L << (r_longlong.BITS-1) f1 = rbigint.fromlong(max-1)# fits in r_longlong ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Remove unused variable and make these size calculations unsigned
Author: stian Branch: math-improvements Changeset: r92982:1a7dc37b2d5d Date: 2017-11-09 13:37 +0100 http://bitbucket.org/pypy/pypy/changeset/1a7dc37b2d5d/ Log:Remove unused variable and make these size calculations unsigned diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -848,14 +848,14 @@ mod = self.int_and_(digit - 1) else: # Perform -size = self.numdigits() - 1 +size = UDIGIT_TYPE(self.numdigits() - 1) if size > 0: rem = self.widedigit(size) -size -= 1 -while size >= 0: +while size > 0: +size -= 1 rem = ((rem << SHIFT) | self.digit(size)) % digit -size -= 1 + else: rem = self.widedigit(0) % digit @@ -890,13 +890,13 @@ mod = self.int_and_(digit - 1) else: # Perform -size = self.numdigits() - 1 +size = UDIGIT_TYPE(self.numdigits() - 1) + if size > 0: rem = self.widedigit(size) -size -= 1 -while size >= 0: +while size > 0: +size -= 1 rem = ((rem << SHIFT) | self.digit(size)) % digit -size -= 1 else: rem = self.digit(0) % digit @@ -981,7 +981,7 @@ # XXX failed to implement raise ValueError("bigint pow() too negative") -size_b = b.numdigits() +size_b = UDIGIT_TYPE(b.numdigits()) if b.sign == 0: return ONERBIGINT @@ -1040,8 +1040,9 @@ if size_b <= FIVEARY_CUTOFF: # Left-to-right binary exponentiation (HAC Algorithm 14.79) # http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf -size_b -= 1 -while size_b >= 0: + +while size_b > 0: +size_b -= 1 bi = b.digit(size_b) j = 1 << (SHIFT-1) while j != 0: @@ -1049,7 +1050,7 @@ if bi & j: z = _help_mult(z, a, c) j >>= 1 -size_b -= 1 + else: # Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) @@ -1328,7 +1329,7 @@ hishift = SHIFT - loshift z = rbigint([NULLDIGIT] * newsize, self.sign, newsize) i = 0 -inverted = False + while i < newsize: digit = self.udigit(wordshift) if invert and i == 0 and wordshift == 0: ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Dont need widedigit | widedigit, when widedigit | digit will do.
Author: stian Branch: math-improvements Changeset: r92983:5c8e47fa96a6 Date: 2017-11-09 19:08 +0100 http://bitbucket.org/pypy/pypy/changeset/5c8e47fa96a6/ Log:Dont need widedigit | widedigit, when widedigit | digit will do. diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -2049,7 +2049,7 @@ * result in z[0:m], and return the d bits shifted out of the top. """ -carry = _unsigned_widen_digit(0) +carry = 0 #assert 0 <= d and d < SHIFT i = 0 while i < m: @@ -2072,7 +2072,7 @@ #assert 0 <= d and d < SHIFT i = m-1 while i >= 0: -acc = (carry << SHIFT) | a.uwidedigit(i) +acc = (carry << SHIFT) | a.udigit(i) carry = acc & mask z.setdigit(i, acc >> d) i -= 1 @@ -2127,10 +2127,10 @@ else: vtop = v.widedigit(j) << SHIFT #assert vtop <= wm1 -vv = vtop | v.widedigit(abs(j-1)) +vv = vtop | v.digit(abs(j-1)) q = vv / wm1 r = vv % wm1 # This seems to be slightly faster than on widen digits than vv - wm1 * q. -vj2 = v.widedigit(abs(j-2)) +vj2 = v.digit(abs(j-2)) while wm2 * q > ((r << SHIFT) | vj2): q -= 1 r += wm1 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 @@ -144,7 +144,7 @@ rl_op2 = rbigint.fromlong(op2) r1 = rl_op1.mod(rl_op2) r2 = op1 % op2 -print op1, op2 + assert r1.tolong() == r2 def test_int_mod(self): ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Fix translation
Author: stian Branch: math-improvements Changeset: r92988:c961b6f6e3c6 Date: 2017-11-09 21:20 +0100 http://bitbucket.org/pypy/pypy/changeset/c961b6f6e3c6/ Log:Fix translation diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -167,6 +167,7 @@ def __ne__(self, other): return not (self == other) +@specialize.argtype(1) def digit(self, x): """Return the x'th digit, as an int.""" return self._digits[x] @@ -212,13 +213,15 @@ if intval < 0: sign = -1 ival = -r_uint(intval) +carry = ival >> SHIFT elif intval > 0: sign = 1 ival = r_uint(intval) +carry = 0 else: return NULLRBIGINT -carry = ival >> SHIFT + if carry: return rbigint([_store_digit(ival & MASK), _store_digit(carry)], sign, 2) @@ -851,17 +854,17 @@ size = UDIGIT_TYPE(self.numdigits() - 1) if size > 0: -rem = self.widedigit(size) +wrem = self.widedigit(size) while size > 0: size -= 1 -rem = ((rem << SHIFT) | self.digit(size)) % digit - +wrem = ((wrem << SHIFT) | self.digit(size)) % digit +rem = _store_digit(wrem) else: -rem = self.widedigit(0) % digit +rem = _store_digit(self.digit(0) % digit) if rem == 0: return NULLRBIGINT -mod = rbigint([_store_digit(rem)], -1 if self.sign < 0 else 1, 1) +mod = rbigint([rem], -1 if self.sign < 0 else 1, 1) else: div, mod = _divrem(self, other) if mod.sign * other.sign == -1: @@ -893,16 +896,17 @@ size = UDIGIT_TYPE(self.numdigits() - 1) if size > 0: -rem = self.widedigit(size) +wrem = self.widedigit(size) while size > 0: size -= 1 -rem = ((rem << SHIFT) | self.digit(size)) % digit +wrem = ((wrem << SHIFT) | self.digit(size)) % digit +rem = _store_digit(wrem) else: -rem = self.digit(0) % digit +rem = _store_digit(self.digit(0) % digit) if rem == 0: return NULLRBIGINT -mod = rbigint([_store_digit(rem)], -1 if self.sign < 0 else 1, 1) +mod = rbigint([rem], -1 if self.sign < 0 else 1, 1) else: raise ZeroDivisionError("long division or modulo by zero") ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Merge default
Author: stian Branch: math-improvements Changeset: r92987:92d38b4c73a2 Date: 2017-11-09 19:16 +0100 http://bitbucket.org/pypy/pypy/changeset/92d38b4c73a2/ Log:Merge default diff too long, truncating to 2000 out of 6320 lines diff --git a/_pytest/terminal.py b/_pytest/terminal.py --- a/_pytest/terminal.py +++ b/_pytest/terminal.py @@ -366,11 +366,11 @@ EXIT_OK, EXIT_TESTSFAILED, EXIT_INTERRUPTED, EXIT_USAGEERROR, EXIT_NOTESTSCOLLECTED) if exitstatus in summary_exit_codes: -self.config.hook.pytest_terminal_summary(terminalreporter=self) self.summary_errors() self.summary_failures() self.summary_warnings() self.summary_passes() +self.config.hook.pytest_terminal_summary(terminalreporter=self) if exitstatus == EXIT_INTERRUPTED: self._report_keyboardinterrupt() del self._keyboardinterrupt_memo diff --git a/extra_tests/requirements.txt b/extra_tests/requirements.txt new file mode 100644 --- /dev/null +++ b/extra_tests/requirements.txt @@ -0,0 +1,2 @@ +pytest +hypothesis diff --git a/extra_tests/test_bytes.py b/extra_tests/test_bytes.py new file mode 100644 --- /dev/null +++ b/extra_tests/test_bytes.py @@ -0,0 +1,84 @@ +from hypothesis import strategies as st +from hypothesis import given, example + +st_bytestring = st.binary() | st.binary().map(bytearray) + +@given(st_bytestring, st_bytestring, st_bytestring) +def test_find(u, prefix, suffix): +s = prefix + u + suffix +assert 0 <= s.find(u) <= len(prefix) +assert s.find(u, len(prefix), len(s) - len(suffix)) == len(prefix) + +@given(st_bytestring, st_bytestring, st_bytestring) +def test_index(u, prefix, suffix): +s = prefix + u + suffix +assert 0 <= s.index(u) <= len(prefix) +assert s.index(u, len(prefix), len(s) - len(suffix)) == len(prefix) + +@given(st_bytestring, st_bytestring, st_bytestring) +def test_rfind(u, prefix, suffix): +s = prefix + u + suffix +assert s.rfind(u) >= len(prefix) +assert s.rfind(u, len(prefix), len(s) - len(suffix)) == len(prefix) + +@given(st_bytestring, st_bytestring, st_bytestring) +def test_rindex(u, prefix, suffix): +s = prefix + u + suffix +assert s.rindex(u) >= len(prefix) +assert s.rindex(u, len(prefix), len(s) - len(suffix)) == len(prefix) + +def adjust_indices(u, start, end): +if end < 0: +end = max(end + len(u), 0) +else: +end = min(end, len(u)) +if start < 0: +start = max(start + len(u), 0) +return start, end + +@given(st_bytestring, st_bytestring) +def test_startswith_basic(u, v): +assert u.startswith(v) is (u[:len(v)] == v) + +@example(b'x', b'', 1) +@example(b'x', b'', 2) +@given(st_bytestring, st_bytestring, st.integers()) +def test_startswith_start(u, v, start): +expected = u[start:].startswith(v) if v else (start <= len(u)) +assert u.startswith(v, start) is expected + +@example(b'x', b'', 1, 0) +@example(b'xx', b'', -1, 0) +@given(st_bytestring, st_bytestring, st.integers(), st.integers()) +def test_startswith_3(u, v, start, end): +if v: +expected = u[start:end].startswith(v) +else: # CPython leaks implementation details in this case +start0, end0 = adjust_indices(u, start, end) +expected = start0 <= len(u) and start0 <= end0 +assert u.startswith(v, start, end) is expected + +@given(st_bytestring, st_bytestring) +def test_endswith_basic(u, v): +if len(v) > len(u): +assert u.endswith(v) is False +else: +assert u.endswith(v) is (u[len(u) - len(v):] == v) + +@example(b'x', b'', 1) +@example(b'x', b'', 2) +@given(st_bytestring, st_bytestring, st.integers()) +def test_endswith_2(u, v, start): +expected = u[start:].endswith(v) if v else (start <= len(u)) +assert u.endswith(v, start) is expected + +@example(b'x', b'', 1, 0) +@example(b'xx', b'', -1, 0) +@given(st_bytestring, st_bytestring, st.integers(), st.integers()) +def test_endswith_3(u, v, start, end): +if v: +expected = u[start:end].endswith(v) +else: # CPython leaks implementation details in this case +start0, end0 = adjust_indices(u, start, end) +expected = start0 <= len(u) and start0 <= end0 +assert u.endswith(v, start, end) is expected diff --git a/extra_tests/test_unicode.py b/extra_tests/test_unicode.py --- a/extra_tests/test_unicode.py +++ b/extra_tests/test_unicode.py @@ -1,3 +1,4 @@ +import sys import pytest from hypothesis import strategies as st from hypothesis import given, settings, example @@ -32,3 +33,89 @@ @given(s=st.text()) def test_composition(s, norm1, norm2, norm3): assert normalize(norm2, normalize(norm1, s)) == normalize(norm3, s) + +@given(st.text(), st.text(), st.text()) +
[pypy-commit] pypy math-improvements: Remove some unneddecary use of widedigit in _x_mul
Author: stian Branch: math-improvements Changeset: r92992:985fb3488ff0 Date: 2017-11-12 05:28 +0100 http://bitbucket.org/pypy/pypy/changeset/985fb3488ff0/ Log:Remove some unneddecary use of widedigit in _x_mul diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -1753,12 +1753,12 @@ pz += 1 carry >>= SHIFT if carry: -carry += z.uwidedigit(pz) +carry += z.udigit(pz) z.setdigit(pz, carry) pz += 1 carry >>= SHIFT if carry: -z.setdigit(pz, z.uwidedigit(pz) + carry) +z.setdigit(pz, z.udigit(pz) + carry) assert (carry >> SHIFT) == 0 i += 1 z._normalize() @@ -1822,7 +1822,7 @@ pz += 1 carry >>= SHIFT if carry: -z.setdigit(pz, z.uwidedigit(pz) + carry) +z.setdigit(pz, z.udigit(pz) + carry) z._normalize() return z ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Make inplace_divmod unsigned, this makes for a ~20% speed up in long / single digit
Author: stian Branch: math-improvements Changeset: r92993:3c7a6c85f39c Date: 2017-11-12 08:40 +0100 http://bitbucket.org/pypy/pypy/changeset/3c7a6c85f39c/ Log:Make inplace_divmod unsigned, this makes for a ~20% speed up in long / single digit diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -718,7 +718,7 @@ elif a._digits[0] == ONEDIGIT: return rbigint(b._digits[:bsize], a.sign * b.sign, bsize) elif bsize == 1: -res = b.uwidedigit(0) * a.uwidedigit(0) +res = b.uwidedigit(0) * a.udigit(0) carry = res >> SHIFT if carry: return rbigint([_store_digit(res & MASK), _store_digit(carry)], a.sign * b.sign, 2) @@ -1949,13 +1949,13 @@ Divide bigint pin by non-zero digit n, storing quotient in pout, and returning the remainder. It's OK for pin == pout on entry. """ -rem = _widen_digit(0) +rem = _unsigned_widen_digit(0) assert n > 0 and n <= MASK if not size: size = pin.numdigits() size -= 1 while size >= 0: -rem = (rem << SHIFT) | pin.digit(size) +rem = (rem << SHIFT) | pin.udigit(size) hi = rem // n pout.setdigit(size, hi) rem -= hi * n ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Provide two assets to make better code in long multidigit division
Author: stian Branch: math-improvements Changeset: r92994:22373c826010 Date: 2017-11-12 10:29 +0100 http://bitbucket.org/pypy/pypy/changeset/22373c826010/ Log:Provide two assets to make better code in long multidigit division diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -2130,8 +2130,11 @@ vtop = 0 else: vtop = v.widedigit(j) << SHIFT -#assert vtop <= wm1 + vv = vtop | v.digit(abs(j-1)) +# These two hints to make division just as fast as doing it unsigned. +assert vv >= 0 +assert wm1 >= 1 q = vv / wm1 r = vv % wm1 # This seems to be slightly faster than on widen digits than vv - wm1 * q. vj2 = v.digit(abs(j-2)) ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Tweak comment about why we don't do it unsigned.
Author: stian Branch: math-improvements Changeset: r92995:f09288ca6bf9 Date: 2017-11-12 10:36 +0100 http://bitbucket.org/pypy/pypy/changeset/f09288ca6bf9/ Log:Tweak comment about why we don't do it unsigned. diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -2117,7 +2117,7 @@ wm1 = w.widedigit(abs(size_w-1)) wm2 = w.widedigit(abs(size_w-2)) - + j = size_v - 1 k -= 1 while k >= 0: @@ -2132,7 +2132,7 @@ vtop = v.widedigit(j) << SHIFT vv = vtop | v.digit(abs(j-1)) -# These two hints to make division just as fast as doing it unsigned. +# Hints to make division just as fast as doing it unsigned. But avoids casting to get correct results. assert vv >= 0 assert wm1 >= 1 q = vv / wm1 ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Fix ulllong division OP in rtyper
Author: stian Branch: math-improvements Changeset: r92997:8b41193b43b2 Date: 2017-11-12 21:10 +0100 http://bitbucket.org/pypy/pypy/changeset/8b41193b43b2/ Log:Fix ulllong division OP in rtyper diff --git a/rpython/rtyper/rint.py b/rpython/rtyper/rint.py --- a/rpython/rtyper/rint.py +++ b/rpython/rtyper/rint.py @@ -476,7 +476,7 @@ @jit.dont_look_inside def ll_ulllong_py_div(x, y): -return llop.ullong_floordiv(UnsignedLongLongLong, x, y) +return llop.ulllong_floordiv(UnsignedLongLongLong, x, y) def ll_ulllong_py_div_zer(x, y): if y == 0: ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Remove invert logic from rqshift (it is only used with positive numbers)
Author: stian Branch: math-improvements Changeset: r93002:3f4aca709e49 Date: 2017-11-13 13:53 +0100 http://bitbucket.org/pypy/pypy/changeset/3f4aca709e49/ Log:Remove invert logic from rqshift (it is only used with positive numbers) diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -1314,38 +1314,22 @@ wordshift = int_other / SHIFT loshift = int_other % SHIFT newsize = self.numdigits() - wordshift - -invert = False -if self.sign == -1: -first = self.digit(0) -if first == 0: -a = self.invert().rqshift(int_other) -return a.invert() -invert = True if newsize <= 0: -if invert: -return ONENEGATIVERBIGINT -else: -return NULLRBIGINT +return NULLRBIGINT - hishift = SHIFT - loshift z = rbigint([NULLDIGIT] * newsize, self.sign, newsize) i = 0 while i < newsize: digit = self.udigit(wordshift) -if invert and i == 0 and wordshift == 0: -digit -= 1 newdigit = (digit >> loshift) if i+1 < newsize: newdigit |= (self.udigit(wordshift+1) << hishift) z.setdigit(i, newdigit) i += 1 -wordshift += 1 -if invert: -z.setdigit(0, z.digit(0)+1) +wordshift += 1 z._normalize() return z rshift._always_inline_ = 'try' # It's so fast that it's always benefitial. 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 @@ -609,21 +609,18 @@ res1 = f1.lqshift(z).tolong() res2 = f1.rqshift(z).tolong() res3 = nf1.lqshift(z).tolong() -res4 = nf1.rqshift(z).tolong() + assert res1 == num << z assert res2 == num >> z assert res3 == -num << z -assert res4 == -num >> z -# Large digit, also invertion test. + +# Large digit for x in range((1 << SHIFT) - 10, (1 << SHIFT) + 10): f1 = rbigint.fromlong(x) -nf1 = rbigint.fromlong(-x) assert f1.rqshift(SHIFT).tolong() == x >> SHIFT -assert nf1.rqshift(SHIFT).tolong() == -x >> SHIFT assert f1.rqshift(SHIFT+1).tolong() == x >> (SHIFT+1) -assert nf1.rqshift(SHIFT+1).tolong() == -x >> (SHIFT+1) def test_from_list_n_bits(self): for x in ([3L ** 30L, 5L ** 20L, 7 ** 300] + ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Don't return a copy on long // 1
Author: stian Branch: math-improvements Changeset: r93012:9838b9ca2938 Date: 2017-11-14 11:18 +0100 http://bitbucket.org/pypy/pypy/changeset/9838b9ca2938/ Log:Don't return a copy on long // 1 diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -788,8 +788,8 @@ if self.sign == 1 and other.numdigits() == 1 and other.sign == 1: digit = other.digit(0) if digit == 1: -return rbigint(self._digits[:self.numdigits()], 1, self.numdigits()) -elif digit and digit & (digit - 1) == 0: +return self +elif digit & (digit - 1) == 0: return self.rqshift(ptwotable[digit]) div, mod = _divrem(self, other) ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Test and fix for int rbinop overflow to long, also add a deeper test for int_floordiv
Author: stian Branch: math-improvements Changeset: r93092:e6c9af023bc5 Date: 2017-11-20 14:19 +0100 http://bitbucket.org/pypy/pypy/changeset/e6c9af023bc5/ Log:Test and fix for int rbinop overflow to long, also add a deeper test for int_floordiv diff --git a/pypy/objspace/std/intobject.py b/pypy/objspace/std/intobject.py --- a/pypy/objspace/std/intobject.py +++ b/pypy/objspace/std/intobject.py @@ -589,7 +589,7 @@ try: return func(space, y, x) except OverflowError: -return ovf2long(space, y, x, w_other) +return ovf2long(space, y, x, self) else: return func(space, y, x) diff --git a/pypy/objspace/std/test/test_intobject.py b/pypy/objspace/std/test/test_intobject.py --- a/pypy/objspace/std/test/test_intobject.py +++ b/pypy/objspace/std/test/test_intobject.py @@ -613,6 +613,9 @@ assert type(x) is int assert str(x) == "0" +def test_rbinop_overflow(self): +x = int(321) +assert x.__rlshift__(333) == 1422567365923326114875084456308921708325401211889530744784729710809598337369906606315292749899759616L class AppTestIntShortcut(AppTestInt): spaceconfig = {"objspace.std.intshortcut": True} 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 @@ -70,6 +70,15 @@ r2 = r.int_floordiv(10) assert r2.tolong() == 100L +for op1 in gen_signs(long_vals): +for op2 in gen_signs(long_vals): +if not op2 or op2 >= (1 << SHIFT) or op2 <= -(1 << SHIFT): +continue +rl_op1 = rbigint.fromlong(op1) +r1 = rl_op1.int_floordiv(op2) +r2 = op1 // op2 +assert r1.tolong() == r2 + assert py.test.raises(ZeroDivisionError, r.int_floordiv, 0) # Error pointed out by Armin Rigo ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Add test for overflow with regular binops too, now there should be test for all changes to intobject
Author: stian Branch: math-improvements Changeset: r93093:89a762f37f25 Date: 2017-11-20 14:32 +0100 http://bitbucket.org/pypy/pypy/changeset/89a762f37f25/ Log:Add test for overflow with regular binops too, now there should be test for all changes to intobject diff --git a/pypy/objspace/std/test/test_intobject.py b/pypy/objspace/std/test/test_intobject.py --- a/pypy/objspace/std/test/test_intobject.py +++ b/pypy/objspace/std/test/test_intobject.py @@ -613,6 +613,10 @@ assert type(x) is int assert str(x) == "0" +def test_binop_overflow(self): +x = int(2) +assert x.__lshift__(128) == 680564733841876926926749214863536422912L + def test_rbinop_overflow(self): x = int(321) assert x.__rlshift__(333) == 1422567365923326114875084456308921708325401211889530744784729710809598337369906606315292749899759616L ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Test for int_pow, test+fix for pow ValueError with third argument as 0
Author: stian Branch: math-improvements Changeset: r93094:9291ee92df89 Date: 2017-11-20 15:01 +0100 http://bitbucket.org/pypy/pypy/changeset/9291ee92df89/ Log:Test for int_pow, test+fix for pow ValueError with third argument as 0 diff --git a/pypy/objspace/std/test/test_longobject.py b/pypy/objspace/std/test/test_longobject.py --- a/pypy/objspace/std/test/test_longobject.py +++ b/pypy/objspace/std/test/test_longobject.py @@ -192,6 +192,12 @@ assert pow(x, 0L, 1L) == 0L assert pow(-1L, -1L) == -1.0 +def test_int_pow(self): +x = 2L +assert pow(x, 2) == 4L +assert pow(x, 2, 2) == 0L +assert pow(x, 2, 3L) == 1L + def test_getnewargs(self): assert 0L .__getnewargs__() == (0L,) assert (-1L) .__getnewargs__() == (-1L,) diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -987,9 +987,7 @@ size_b = UDIGIT_TYPE(b.numdigits()) -if b.sign == 0: -return ONERBIGINT -elif c is not None: +if c is not None: if c.sign == 0: raise ValueError("pow() 3rd argument cannot be 0") @@ -1016,6 +1014,8 @@ # so we only do it when it buys something. if a.sign < 0 or a.numdigits() > c.numdigits(): a = a.mod(c) +elif b.sign == 0: +return ONERBIGINT elif a.sign == 0: return NULLRBIGINT elif size_b == 1: @@ -1124,9 +1124,7 @@ raise ValueError("bigint pow() too negative") assert b >= 0 -if b == 0: -return ONERBIGINT -elif c is not None: +if c is not None: if c.sign == 0: raise ValueError("pow() 3rd argument cannot be 0") @@ -1153,6 +1151,8 @@ # so we only do it when it buys something. if a.sign < 0 or a.numdigits() > c.numdigits(): a = a.mod(c) +elif b == 0: +return ONERBIGINT elif a.sign == 0: return NULLRBIGINT elif b == 1: 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 @@ -190,7 +190,12 @@ r4 = pow(op1, op2, 1000) print op1, op2 assert r3.tolong() == r4 - + +def test_pow_raises(self): +r1 = rbigint.fromint(2) +r0 = rbigint.fromint(0) +py.test.raises(ValueError, r1.int_pow, 2, r0) +py.test.raises(ValueError, r1.pow, r1, r0) def test_touint(self): result = r_uint(sys.maxint + 42) rl = rbigint.fromint(sys.maxint).add(rbigint.fromint(42)) ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy math-improvements: Typo in comment
Author: stian Branch: math-improvements Changeset: r93095:6ba5b9334842 Date: 2017-11-20 15:08 +0100 http://bitbucket.org/pypy/pypy/changeset/6ba5b9334842/ Log:Typo in comment diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py --- a/rpython/rlib/rbigint.py +++ b/rpython/rlib/rbigint.py @@ -2120,7 +2120,7 @@ assert vv >= 0 assert wm1 >= 1 q = vv / wm1 -r = vv % wm1 # This seems to be slightly faster than on widen digits than vv - wm1 * q. +r = vv % wm1 # This seems to be slightly faster on widen digits than vv - wm1 * q. vj2 = v.digit(abs(j-2)) while wm2 * q > ((r << SHIFT) | vj2): q -= 1 ___ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Re-enable the a == b strategy. Apperently it works, thou, not 2x speedup, but 16% on HUGE ints
Author: stian Branch: improve-rbigint Changeset: r56314:ce7c8412e355 Date: 2012-06-22 02:57 +0200 http://bitbucket.org/pypy/pypy/changeset/ce7c8412e355/ Log:Re-enable the a == b strategy. Apperently it works, thou, not 2x speedup, but 16% on HUGE ints diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -857,16 +857,26 @@ """ size_a = a.numdigits() -size_b = b.numdigits() -""" -# Code below actually runs slower (about 20%). Dunno why, since it shouldn't. + +if size_a == 1: +# Special case. +digit = a.digit(0) +if digit == 0: +return rbigint([NULLDIGIT], 1) +elif digit == 1: +return rbigint(b._digits[:], 1) +elif digit & (digit - 1) == 0: +return b.lqshift(ptwotable[digit]) + +size_b = b.numdigits() +z = rbigint([NULLDIGIT] * (size_a + size_b), 1) +i = 0 if a is b: # Efficient squaring per HAC, Algorithm 14.16: # http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf # Gives slightly less than a 2x speedup when a == b, # via exploiting that each entry in the multiplication # pyramid appears twice (except for the size_a squares). -i = 0 while i < size_a: f = a.widedigit(i) pz = i << 1 @@ -898,36 +908,25 @@ z.setdigit(pz, z.widedigit(pz) + carry) assert (carry >> SHIFT) == 0 i += 1 -else:""" -if size_a == 1: -# Special case. -digit = a.digit(0) -if digit == 0: -return rbigint([NULLDIGIT], 1) -elif digit == 1: -return rbigint(b._digits[:], 1) -elif digit & (digit - 1) == 0: -return b.lqshift(ptwotable[digit]) - -z = rbigint([NULLDIGIT] * (size_a + size_b), 1) -# gradeschool long mult -i = 0 -while i < size_a: -carry = 0 -f = a.widedigit(i) -pz = i -pb = 0 -while pb < size_b: -carry += z.widedigit(pz) + b.widedigit(pb) * f -pb += 1 -z.setdigit(pz, carry) -pz += 1 -carry >>= SHIFT -assert carry <= MASK -if carry: -z.setdigit(pz, z.widedigit(pz) + carry) -assert (carry >> SHIFT) == 0 -i += 1 +else: +# gradeschool long mult +while i < size_a: +carry = 0 +f = a.widedigit(i) +pz = i +pb = 0 +while pb < size_b: +carry += z.widedigit(pz) + b.widedigit(pb) * f +pb += 1 +z.setdigit(pz, carry) +pz += 1 +carry >>= SHIFT +assert carry <= MASK +if carry: +z.setdigit(pz, z.widedigit(pz) + carry) +assert (carry >> SHIFT) == 0 +i += 1 + z._normalize() return z ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Move the strategy for _x_mul
Author: stian Branch: improve-rbigint Changeset: r56315:e524f7977e76 Date: 2012-06-22 03:33 +0200 http://bitbucket.org/pypy/pypy/changeset/e524f7977e76/ Log:Move the strategy for _x_mul diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -857,26 +857,25 @@ """ size_a = a.numdigits() - + if size_a == 1: # Special case. digit = a.digit(0) if digit == 0: return rbigint([NULLDIGIT], 1) elif digit == 1: -return rbigint(b._digits[:], 1) -elif digit & (digit - 1) == 0: -return b.lqshift(ptwotable[digit]) +return rbigint([b._digits[0]], 1) -size_b = b.numdigits() -z = rbigint([NULLDIGIT] * (size_a + size_b), 1) -i = 0 +size_b = b.numdigits() + if a is b: # Efficient squaring per HAC, Algorithm 14.16: # http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf # Gives slightly less than a 2x speedup when a == b, # via exploiting that each entry in the multiplication # pyramid appears twice (except for the size_a squares). +z = rbigint([NULLDIGIT] * (size_a + size_b), 1) +i = 0 while i < size_a: f = a.widedigit(i) pz = i << 1 @@ -908,8 +907,17 @@ z.setdigit(pz, z.widedigit(pz) + carry) assert (carry >> SHIFT) == 0 i += 1 +z._normalize() +return z else: +if size_a == 1: +digit = a.digit(0) +if digit & (digit - 1) == 0: +return b.lqshift(ptwotable[digit]) + +z = rbigint([NULLDIGIT] * (size_a + size_b), 1) # gradeschool long mult +i = 0 while i < size_a: carry = 0 f = a.widedigit(i) @@ -926,9 +934,8 @@ z.setdigit(pz, z.widedigit(pz) + carry) assert (carry >> SHIFT) == 0 i += 1 - -z._normalize() -return z +z._normalize() +return z def _kmul_split(n, size): ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Futher improvements, two more tests
Author: stian Branch: improve-rbigint Changeset: r56318:fb9c7d03ec58 Date: 2012-06-22 23:37 +0200 http://bitbucket.org/pypy/pypy/changeset/fb9c7d03ec58/ Log:Futher improvements, two more tests diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -93,9 +93,7 @@ class rbigint(object): """This is a reimplementation of longs using a list of digits.""" -def __init__(self, digits=[], sign=0): -if len(digits) == 0: -digits = [NULLDIGIT] +def __init__(self, digits=[NULLDIGIT], sign=0): _check_digits(digits) make_sure_not_resized(digits) self._digits = digits @@ -374,7 +372,7 @@ result = _x_mul(self, other) result.sign = self.sign * other.sign return result - + def truediv(self, other): div = _bigint_true_divide(self, other) return div @@ -450,27 +448,29 @@ if a.sign < 0: a, temp = a.divmod(c) a = temp - + +size_b = b.numdigits() + # At this point a, b, and c are guaranteed non-negative UNLESS # c is NULL, in which case a may be negative. */ -z = rbigint([_store_digit(1)], 1) - +z = rbigint([ONEDIGIT], 1) + # python adaptation: moved macros REDUCE(X) and MULT(X, Y, result) # into helper function result = _help_mult(x, y, c) -if b.numdigits() <= FIVEARY_CUTOFF: +if not c or size_b <= FIVEARY_CUTOFF: # Left-to-right binary exponentiation (HAC Algorithm 14.79) # http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf -i = b.numdigits() - 1 -while i >= 0: -bi = b.digit(i) +size_b -= 1 +while size_b >= 0: +bi = b.digit(size_b) j = 1 << (SHIFT-1) while j != 0: z = _help_mult(z, z, c) if bi & j: z = _help_mult(z, a, c) j >>= 1 -i -= 1 +size_b -= 1 else: # Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) # This is only useful in the case where c != None. @@ -479,7 +479,7 @@ table[0] = z for i in range(1, 32): table[i] = _help_mult(table[i-1], a, c) -i = b.numdigits() + # Note that here SHIFT is not a multiple of 5. The difficulty # is to extract 5 bits at a time from 'b', starting from the # most significant digits, so that at the end of the algorithm @@ -488,11 +488,11 @@ # m+ = m rounded up to the next multiple of 5 # j = (m+) % SHIFT = (m+) - (i * SHIFT) # (computed without doing "i * SHIFT", which might overflow) -j = i % 5 +j = size_b % 5 if j != 0: j = 5 - j if not we_are_translated(): -assert j == (i*SHIFT+4)//5*5 - i*SHIFT +assert j == (size_b*SHIFT+4)//5*5 - size_b*SHIFT # accum = r_uint(0) while True: @@ -502,10 +502,12 @@ else: # 'accum' does not have enough digit. # must get the next digit from 'b' in order to complete -i -= 1 -if i < 0: -break# done -bi = b.udigit(i) +if size_b == 0: +break # Done + +size_b -= 1 + +bi = b.udigit(size_b) index = ((accum << (-j)) | (bi >> (j+SHIFT))) & 0x1f accum = bi j += SHIFT @@ -563,13 +565,11 @@ def lqshift(self, int_other): " A quicker one with much less checks, int_other is valid and for the most part constant." -if int_other == 0: -return self +assert int_other > 0 oldsize = self.numdigits() -newsize = oldsize + 1 -z = rbigint([NULLDIGIT] * newsize, self.sign) +z = rbigint([NULLDIGIT] * (oldsize + 1), self.sign) accum = _widen_digit(0) for i in range(oldsize): @@ -577,7 +577,7 @@ z.setdigit(i, accum) accum >>= SHIFT -z.setdigit(newsize - 1, accum) +z.setdigit(oldsize, accum) z._normalize() return z @@ -701,12 +701,10 @@ # Perform a modular reduction, X = X % c, but leave X alone if c # is NULL. if c is not None: -res, temp = res.divmod(c) -res = temp +temp, res = res.divmod(c) +
[pypy-commit] pypy improve-rbigint: Power of two improvements?
Author: stian Branch: improve-rbigint Changeset: r56323:255c21cf7d24 Date: 2012-06-24 07:49 +0200 http://bitbucket.org/pypy/pypy/changeset/255c21cf7d24/ Log:Power of two improvements? diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -484,7 +484,20 @@ a = temp size_b = b.numdigits() - + +if not c and size_b == 1 and a.sign == 1: +digit = b.digit(0) +if digit == 0: +return rbigint([ONEDIGIT], 1) +elif digit == 1: +return a +elif a.numdigits() == 1: +adigit = a.digit(0) +if adigit == 1: +return rbigint([ONEDIGIT], 1) +elif adigit == 2: +return a.lshift(digit-1) + # At this point a, b, and c are guaranteed non-negative UNLESS # c is NULL, in which case a may be negative. */ diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -19,6 +19,7 @@ 6.647562 Pypy with improvements: +9.474363 5.797121 10.068798 14.770187 @@ -28,6 +29,14 @@ 6.440351 """ + +t = time() +num = rbigint.fromint(1000) +for n in xrange(1): +rbigint.pow(rbigint.fromint(2), num) + + +print time() - t t = time() num = rbigint.pow(rbigint.fromint(1), rbigint.fromint(2 ** 8)) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Forgot pypy default results (300 times faster with improvements)
Author: stian Branch: improve-rbigint Changeset: r56326:df00c7f6973b Date: 2012-06-24 21:57 +0200 http://bitbucket.org/pypy/pypy/changeset/df00c7f6973b/ Log:Forgot pypy default results (300 times faster with improvements) diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -11,6 +11,7 @@ A cutout with some benchmarks. Pypy default: 484.5688 +334.611903 8.637287 12.211942 18.270045 @@ -32,13 +33,13 @@ """ -"""t = time() +t = time() num = rbigint.fromint(1000) for n in xrange(1): rbigint.pow(rbigint.fromint(2), num) -print time() - t""" +print time() - t t = time() num = rbigint.fromint(1) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Fix translation of targetpypystandalone when SHIFT != 31
Author: stian Branch: improve-rbigint Changeset: r56332:c2fc7b58dbe8 Date: 2012-06-25 08:22 +0200 http://bitbucket.org/pypy/pypy/changeset/c2fc7b58dbe8/ Log:Fix translation of targetpypystandalone when SHIFT != 31 It translate, in jit mode on 64bit now :) diff --git a/pypy/module/sys/system.py b/pypy/module/sys/system.py --- a/pypy/module/sys/system.py +++ b/pypy/module/sys/system.py @@ -47,8 +47,8 @@ return space.call_function(w_float_info, space.newtuple(info_w)) def get_long_info(space): -assert rbigint.SHIFT == 31 -bits_per_digit = rbigint.SHIFT +#assert rbigint.SHIFT == 31 +bits_per_digit = 31 #rbigint.SHIFT sizeof_digit = rffi.sizeof(rffi.ULONG) info_w = [ space.wrap(bits_per_digit), diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -564,7 +564,7 @@ size_b -= 1 else: -# XXX: Not working with int128! +# XXX: Not working with int128! Yet # Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) # This is only useful in the case where c != None. # z still holds 1L @@ -582,8 +582,8 @@ # j = (m+) % SHIFT = (m+) - (i * SHIFT) # (computed without doing "i * SHIFT", which might overflow) j = size_b % 5 -if j != 0: -j = 5 - j +"""if j != 0: +j = 5 - j""" if not we_are_translated(): assert j == (size_b*SHIFT+4)//5*5 - size_b*SHIFT # @@ -611,7 +611,7 @@ z = _help_mult(z, table[index], c) # assert j == -5 - + if negativeOutput and z.sign != 0: z = z.sub(c) return z ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Fix a test, fix so all tests passes, and some improvements.
Author: stian Branch: improve-rbigint Changeset: r56335:a503b84e2d2f Date: 2012-06-26 00:44 +0200 http://bitbucket.org/pypy/pypy/changeset/a503b84e2d2f/ Log:Fix a test, fix so all tests passes, and some improvements. Minor impact on performance, some become faster, some slower. I'll see how it turns out in a translated version. diff --git a/pypy/rlib/rarithmetic.py b/pypy/rlib/rarithmetic.py --- a/pypy/rlib/rarithmetic.py +++ b/pypy/rlib/rarithmetic.py @@ -115,26 +115,25 @@ n -= 2*LONG_TEST return int(n) -def longlongmask(n): -""" -NOT_RPYTHON -""" -assert isinstance(n, (int, long)) -n = long(n) -n &= LONGLONG_MASK -if n >= LONGLONG_TEST: -n -= 2*LONGLONG_TEST -return r_longlong(n) +if LONG_BIT >= 64: +def longlongmask(n): +assert isinstance(n, (int, long)) +return int(n) +else: +def longlongmask(n): +""" +NOT_RPYTHON +""" +assert isinstance(n, (int, long)) +n = long(n) +n &= LONGLONG_MASK +if n >= LONGLONG_TEST: +n -= 2*LONGLONG_TEST +return r_longlong(n) def longlonglongmask(n): -""" -NOT_RPYTHON -""" -assert isinstance(n, (int, long)) -n = long(n) -n &= LONGLONGLONG_MASK -if n >= LONGLONGLONG_TEST: -n -= 2*LONGLONGLONG_TEST +# Assume longlonglong doesn't overflow. This is perfectly fine for rbigint. +# We deal directly with overflow there anyway. return r_longlonglong(n) def widen(n): diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -1,4 +1,4 @@ -from pypy.rlib.rarithmetic import LONG_BIT, intmask, longlongmask, r_uint, r_ulonglong, r_longlonglong +from pypy.rlib.rarithmetic import LONG_BIT, intmask, longlongmask, r_uint, r_int, r_ulonglong, r_longlonglong from pypy.rlib.rarithmetic import ovfcheck, r_longlong, widen, is_valid_int from pypy.rlib.rarithmetic import most_neg_value_of_same_type from pypy.rlib.rfloat import isfinite @@ -55,10 +55,11 @@ def _widen_digit(x): """if not we_are_translated(): assert is_valid_int(x), "widen_digit() takes an int, got a %r" % type(x)""" -return r_longlonglong(x) -"""if LONG_BIT < 64: +if SHIFT > 31: +# XXX: Using rffi.cast is probably quicker, but I dunno how to get it working. +return r_longlonglong(x) +else: return r_longlong(x) -return x""" def _store_digit(x): """if not we_are_translated(): @@ -71,14 +72,22 @@ return rffi.cast(rffi.LONGLONG, x) else: raise ValueError("SHIFT too large!") +_store_digit._annspecialcase_ = 'specialize:argtype(0)' def _load_digit(x): -return x -#return rffi.cast(lltype.Signed, x) +if SHIFT < LONG_BIT: # This would be the case for any SHIFT < LONG_BIT +return rffi.cast(lltype.Signed, x) +else: +# x already is a type large enough, just not as fast. +return x def _load_unsigned_digit(x): -return r_ulonglong(x) -#return rffi.cast(lltype.Unsigned, x) +if SHIFT < LONG_BIT: # This would be the case for any SHIFT < LONG_BIT +return rffi.cast(lltype.Unsigned, x) +else: +# This needs a performance test on 32bit +return rffi.cast(rffi.ULONGLONG, x) +#return r_ulonglong(x) NULLDIGIT = _store_digit(0) ONEDIGIT = _store_digit(1) @@ -86,8 +95,7 @@ def _check_digits(l): for x in l: assert type(x) is type(NULLDIGIT) -# XXX: Fix for int128 -# assert intmask(x) & MASK == intmask(x) +assert longlongmask(x) & MASK == longlongmask(x) class Entry(extregistry.ExtRegistryEntry): _about_ = _check_digits @@ -621,7 +629,7 @@ return rbigint(self._digits, abs(self.sign)) def invert(self): #Implement ~x as -(x + 1) -return self.add(rbigint([_store_digit(1)], 1)).neg() +return self.add(ONERBIGINT).neg() def lshift(self, int_other): if int_other < 0: @@ -783,7 +791,7 @@ INTCACHE = {} for x in range(1, CACHE_INTS+1): -numList = [_store_digit(x)] +numList = [_store_digit(_mask_digit(x))] INTCACHE[x] = rbigint(numList, 1) INTCACHE[-x] = rbigint(numList, -1) @@ -811,7 +819,7 @@ def digits_from_nonneg_long(l): digits = [] while True: -digits.append(_store_digit(intmask(l & MASK))) +digits.append(_store_digit(_mask_digit(l & MASK))) l = l >> SHIFT if not l: return digits[:] # to make it non-resizable @@ -894,7 +902,7 @@ # Special casing. if a is b: -return rbigint([NULLDIGIT], 1) +return NULLR
[pypy-commit] pypy improve-rbigint: Some not working code for checking for int128 support. Also add support for non-int128 platforms as soon as we can detect them.
Author: stian Branch: improve-rbigint Changeset: r56336:e8c1863ac3e4 Date: 2012-06-26 02:45 +0200 http://bitbucket.org/pypy/pypy/changeset/e8c1863ac3e4/ Log:Some not working code for checking for int128 support. Also add support for non-int128 platforms as soon as we can detect them. diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -7,17 +7,35 @@ from pypy.rlib import jit from pypy.rpython.lltypesystem import lltype, rffi from pypy.rpython import extregistry +from pypy.rpython.tool import rffi_platform +from pypy.translator.tool.cbuild import ExternalCompilationInfo import math, sys +# Check for int128 support. Is this right? It sure doesn't work. +"""class CConfig: +_compilation_info_ = ExternalCompilationInfo() + +__INT128 = rffi_platform.SimpleType("__int128", rffi.__INT128) + +cConfig = rffi_platform.configure(CConfig)""" + +SUPPORT_INT128 = True + # note about digit sizes: # In division, the native integer type must be able to hold # a sign bit plus two digits plus 1 overflow bit. #SHIFT = (LONG_BIT // 2) - 1 -SHIFT = 63 - -MASK = long((1 << SHIFT) - 1) +if SUPPORT_INT128: +SHIFT = 63 +MASK = long((1 << SHIFT) - 1) +UDIGIT_TYPE = r_ulonglong +else: +SHIFT = 31 +MASK = int((1 << SHIFT) - 1) +UDIGIT_TYPE = r_uint + FLOAT_MULTIPLIER = float(1 << LONG_BIT) # Because it works. CACHE_INTS = 1024 # CPython do 256 @@ -34,7 +52,12 @@ # Karatsuba is O(N**1.585) USE_KARATSUBA = True # set to False for comparison -KARATSUBA_CUTOFF = 19 #38 + +if SHIFT > 31: +KARATSUBA_CUTOFF = 19 +else: +KARATSUBA_CUTOFF = 38 + KARATSUBA_SQUARE_CUTOFF = 2 * KARATSUBA_CUTOFF USE_TOOMCOCK = False # WIP @@ -48,8 +71,13 @@ FIVEARY_CUTOFF = 8 -def _mask_digit(x): -return longlongmask(x & MASK) #intmask(x & MASK) +if SHIFT <= 31: +def _mask_digit(x): +return intmask(x & MASK) +else: +def _mask_digit(x): +return longlongmask(x & MASK) + _mask_digit._annspecialcase_ = 'specialize:argtype(0)' def _widen_digit(x): @@ -95,7 +123,10 @@ def _check_digits(l): for x in l: assert type(x) is type(NULLDIGIT) -assert longlongmask(x) & MASK == longlongmask(x) +if SHIFT <= 31: +assert intmask(x) & MASK == intmask(x) +else: +assert longlongmask(x) & MASK == longlongmask(x) class Entry(extregistry.ExtRegistryEntry): _about_ = _check_digits @@ -882,7 +913,7 @@ size_a, size_b = size_b, size_a z = rbigint([NULLDIGIT] * (size_a + 1), 1) i = 0 -carry = r_ulonglong(0) +carry = UDIGIT_TYPE(0) while i < size_b: carry += a.udigit(i) + b.udigit(i) z.setdigit(i, carry) @@ -926,7 +957,7 @@ size_a = size_b = i+1 z = rbigint([NULLDIGIT] * size_a, sign) -borrow = r_ulonglong(0) +borrow = UDIGIT_TYPE(0) i = 0 while i < size_b: # The following assumes unsigned arithmetic @@ -1430,7 +1461,7 @@ def _x_divrem(v1, w1): """ Unsigned bigint division with remainder -- the algorithm """ size_w = w1.numdigits() -d = (r_ulonglong(MASK)+1) // (w1.udigit(size_w-1) + 1) +d = (UDIGIT_TYPE(MASK)+1) // (w1.udigit(size_w-1) + 1) assert d <= MASK# because the first digit of w1 is not zero d = longlongmask(d) v = _muladd1(v1, d) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Add some jit hooks and remove the shift len check from int.h (because rbigint is the only place we use longlonglong, and probably ever gonna use it)
Author: stian Branch: improve-rbigint Changeset: r56340:89890e8a28a8 Date: 2012-06-27 05:17 +0200 http://bitbucket.org/pypy/pypy/changeset/89890e8a28a8/ Log:Add some jit hooks and remove the shift len check from int.h (because rbigint is the only place we use longlonglong, and probably ever gonna use it) diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -232,6 +232,7 @@ return rbigint(*args_from_long(l)) @staticmethod +@jit.elidable def fromfloat(dval): """ Create a new bigint object from a float """ # This function is not marked as pure because it can raise @@ -328,20 +329,25 @@ """Return r_ulonglong(self), truncating.""" return _AsULonglong_mask(self) +@jit.elidable def tofloat(self): return _AsDouble(self) +@jit.elidable def format(self, digits, prefix='', suffix=''): # 'digits' is a string whose length is the base to use, # and where each character is the corresponding digit. return _format(self, digits, prefix, suffix) +@jit.elidable def repr(self): return _format(self, BASE10, '', 'L') +@jit.elidable def str(self): return _format(self, BASE10) +@jit.elidable def eq(self, other): if (self.sign != other.sign or self.numdigits() != other.numdigits()): @@ -401,9 +407,11 @@ def ge(self, other): return not self.lt(other) +@jit.elidable def hash(self): return _hash(self) +@jit.elidable def add(self, other): if self.sign == 0: return other @@ -416,6 +424,7 @@ result.sign *= other.sign return result +@jit.elidable def sub(self, other): if other.sign == 0: return self @@ -429,6 +438,7 @@ result._normalize() return result +@jit.elidable def mul(self, b): asize = self.numdigits() bsize = b.numdigits() @@ -477,11 +487,13 @@ result.sign = a.sign * b.sign return result - + +@jit.elidable def truediv(self, other): div = _bigint_true_divide(self, other) return div +@jit.elidable def floordiv(self, other): if other.numdigits() == 1 and other.sign == 1: digit = other.digit(0) @@ -495,15 +507,18 @@ div = div.sub(ONERBIGINT) return div +@jit.elidable def div(self, other): return self.floordiv(other) +@jit.elidable def mod(self, other): div, mod = _divrem(self, other) if mod.sign * other.sign == -1: mod = mod.add(other) return mod +@jit.elidable def divmod(v, w): """ The / and % operators are now defined in terms of divmod(). @@ -527,6 +542,7 @@ div = div.sub(ONERBIGINT) return div, mod +@jit.elidable def pow(a, b, c=None): negativeOutput = False # if x<0 return negative output @@ -663,6 +679,7 @@ def invert(self): #Implement ~x as -(x + 1) return self.add(ONERBIGINT).neg() +@jit.elidable def lshift(self, int_other): if int_other < 0: raise ValueError("negative shift count") @@ -696,6 +713,7 @@ z._normalize() return z +@jit.elidable def lqshift(self, int_other): " A quicker one with much less checks, int_other is valid and for the most part constant." assert int_other > 0 @@ -714,6 +732,7 @@ z._normalize() return z +@jit.elidable def rshift(self, int_other, dont_invert=False): if int_other < 0: raise ValueError("negative shift count") @@ -747,12 +766,15 @@ z._normalize() return z +@jit.elidable def and_(self, other): return _bitwise(self, '&', other) +@jit.elidable def xor(self, other): return _bitwise(self, '^', other) +@jit.elidable def or_(self, other): return _bitwise(self, '|', other) @@ -765,6 +787,7 @@ def hex(self): return _format(self, BASE16, '0x', 'L') +@jit.elidable def log(self, base): # base is supposed to be positive or 0.0, which means we use e if base == 10.0: diff --git a/pypy/translator/c/src/int.h b/pypy/translator/c/src/int.h --- a/pypy/translator/c/src/int.h +++ b/pypy/translator/c/src/int.h @@ -98,8 +98,7 @@ r = Py_ARITHMETIC_RIGHT_SHIFT(PY_LONG_LONG,x, (y)) #define OP_ULLONG_RSHIFT(x,y,r) CHECK_SHIFT_RANGE(y, PYPY_LONGLONG_BIT); \
[pypy-commit] pypy improve-rbigint: Some more test data, and removal of the intcache stuff (In jit mode, this doesn't matter, I benchmarked in opt=2)
Author: stian Branch: improve-rbigint Changeset: r56342:5a437e212443 Date: 2012-06-28 00:34 +0200 http://bitbucket.org/pypy/pypy/changeset/5a437e212443/ Log:Some more test data, and removal of the intcache stuff (In jit mode, this doesn't matter, I benchmarked in opt=2) diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -181,10 +181,7 @@ # This function is marked as pure, so you must not call it and # then modify the result. check_regular_int(intval) - -if intval != 0 and intval <= CACHE_INTS and intval >= -CACHE_INTS: -return INTCACHE[intval] - + if intval < 0: sign = -1 ival = r_uint(-intval) @@ -848,12 +845,7 @@ return "" % (self._digits, self.sign, self.str()) -INTCACHE = {} -for x in range(1, CACHE_INTS+1): -numList = [_store_digit(_mask_digit(x))] -INTCACHE[x] = rbigint(numList, 1) -INTCACHE[-x] = rbigint(numList, -1) - + ONERBIGINT = rbigint([ONEDIGIT], 1) NULLRBIGINT = rbigint() @@ -931,7 +923,6 @@ def _x_add(a, b): """ Add the absolute values of two bigint integers. """ - size_a = a.numdigits() size_b = b.numdigits() @@ -1559,19 +1550,18 @@ if vj == wm1: q = MASK +r = 0 else: -q = ((vj << SHIFT) + vj1) // wm1 - +vv = ((vj << SHIFT) | vj1) +q = vv // wm1 +r = _widen_digit(vv) - wm1 * q vj2 = v.widedigit(j-2) -while (wm2 * q > -(( -(vj << SHIFT) -+ vj1 -- q * wm1 -) << SHIFT) -+ vj2): +while wm2 * q > ((r << SHIFT) | vj2): q -= 1 +r += wm1 +if r > MASK: +break i = 0 while i < size_w and i+k < size_v: z = w.widedigit(i) * q diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -12,6 +12,7 @@ A cutout with some benchmarks. Pypy default: +2.777119 2.316023 2.418211 5.147583 @@ -27,21 +28,38 @@ 6.647562 Pypy with improvements: -2.522946 -4.600970 -2.126048 -4.276203 -9.662745 -1.621029 -3.956685 -5.752223 -7.660295 -0.039137 -4.437456 -9.078680 -4.995520 +2.822389 # Little slower, divmod +2.522946 # Little shower, rshift +4.600970 # Much slower, lshift +2.126048 # Twice as fast +4.276203 # Little faster +9.662745 # 50 times faster +1.621029 # 200 times faster +3.956685 # Twice as fast +5.752223 # Twice as fast +7.660295 # More than twice as fast +0.039137 # 50 times faster +4.437456 # 3 times faster +9.078680 # Twice as fast +4.995520 # 1/3 faster, add +A pure python form of those tests where also run +Improved pypy | Pypy | CPython 2.7.3 +0.0440728664398 2.82172012329 1.38699007034 +0.12417101860.1261301040658.17586708069 +0.12434387207 0.1243581771858.34655714035 +0.0627701282501 0.0626962184906 4.88309693336 +0.0636250972748 0.0626759529114 4.88519001007 +1.20847392082 479.282402992 (forever, I yet it run for 5min before quiting) +1.66941714287 (forever) (another forever) +0.0701060295105 6.59566307068 8.29050803185 +6.55810189247 12.1487128735 7.1309800148 +7.59417295456 15.0498359203 11.733394146 +0.001444101333622.13657021523 1.67227101326 +5.06110692024 14.7546520233 9.05311799049 +9.19830608368 17.0125601292 11.1488289833 +5.40441417694 6.59027791023 3.63601899147 """ t = time() ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Refactor the benchmark and make stuff unsigned
Author: stian Branch: improve-rbigint Changeset: r56343:ec8a20c4a39e Date: 2012-07-03 23:53 +0200 http://bitbucket.org/pypy/pypy/changeset/ec8a20c4a39e/ Log:Refactor the benchmark and make stuff unsigned diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -41,8 +41,6 @@ MASK = BASE - 1 FLOAT_MULTIPLIER = float(1 << LONG_BIT) # Because it works. -CACHE_INTS = 1024 # CPython do 256 - # Debugging digit array access. # # False == no checking at all @@ -66,9 +64,6 @@ USE_TOOMCOCK = False # WIP TOOMCOOK_CUTOFF = 3 # Smallest possible cutoff is 3. Ideal is probably around 150+ -# Use N**2 division when number of digits are smaller than this. -DIV_LIMIT = KARATSUBA_CUTOFF - # For exponentiation, use the binary left-to-right algorithm # unless the exponent contains more than FIVEARY_CUTOFF digits. # In that case, do 5 bits at a time. The potential drawback is that @@ -709,7 +704,7 @@ i += 1 j += 1 -z.setdigit(newsize - 1, accum) +z.setdigit(abs(newsize - 1), accum) z._normalize() return z @@ -809,18 +804,18 @@ return l * self.sign def _normalize(self): -i = self.numdigits() +i = _load_unsigned_digit(self.numdigits()) if i == 0: self.sign = 0 self._digits = [NULLDIGIT] return -while i > 1 and self.digit(i - 1) == 0: +while i > 1 and self.udigit(i - 1) == 0: i -= 1 assert i >= 1 if i != self.numdigits(): self._digits = self._digits[:i] -if self.numdigits() == 1 and self.digit(0) == 0: +if self.numdigits() == 1 and self.udigit(0) == 0: self.sign = 0 def bit_length(self): @@ -931,19 +926,22 @@ a, b = b, a size_a, size_b = size_b, size_a z = rbigint([NULLDIGIT] * (size_a + 1), 1) -i = 0 +i = _load_unsigned_digit(0) carry = UDIGIT_TYPE(0) while i < size_b: carry += a.udigit(i) + b.udigit(i) z.setdigit(i, carry) carry >>= SHIFT i += 1 -while i < size_a: +if i < size_a: carry += a.udigit(i) z.setdigit(i, carry) -carry >>= SHIFT i += 1 -z.setdigit(i, carry) +while i < size_a: +z.setdigit(i, a.udigit(i)) +i += 1 +else: +z.setdigit(i, carry) z._normalize() return z @@ -977,7 +975,7 @@ z = rbigint([NULLDIGIT] * size_a, sign) borrow = UDIGIT_TYPE(0) -i = 0 +i = _load_unsigned_digit(0) while i < size_b: # The following assumes unsigned arithmetic # works modulo 2**N for some N>SHIFT. @@ -986,13 +984,15 @@ borrow >>= SHIFT borrow &= 1 # Keep only one sign bit i += 1 -while i < size_a: +if i < size_a: borrow = a.udigit(i) - borrow z.setdigit(i, borrow) -borrow >>= SHIFT -borrow &= 1 # Keep only one sign bit i += 1 -assert borrow == 0 +assert borrow >> 63 == 0 + +while i < size_a: +z.setdigit(i, a.udigit(i)) +i += 1 z._normalize() return z @@ -1018,7 +1018,7 @@ # via exploiting that each entry in the multiplication # pyramid appears twice (except for the size_a squares). z = rbigint([NULLDIGIT] * (size_a + size_b), 1) -i = 0 +i = _load_unsigned_digit(0) while i < size_a: f = a.widedigit(i) pz = i << 1 @@ -1058,7 +1058,7 @@ z = rbigint([NULLDIGIT] * (size_a + size_b), 1) # gradeschool long mult -i = 0 +i = _load_unsigned_digit(0) while i < size_a: carry = 0 f = a.widedigit(i) @@ -1415,7 +1415,7 @@ carry = r_uint(0) assert m >= n -i = xofs +i = _load_unsigned_digit(xofs) iend = xofs + n while i < iend: carry += x.udigit(i) + y.udigit(i-xofs) @@ -1442,7 +1442,7 @@ borrow = r_uint(0) assert m >= n -i = xofs +i = _load_unsigned_digit(xofs) iend = xofs + n while i < iend: borrow = x.udigit(i) - y.udigit(i-xofs) - borrow @@ -1512,7 +1512,7 @@ """ Unsigned bigint division with remainder -- the algorithm """ size_w = w1.numdigits() -d = (UDIGIT_TYPE(MASK)+1) // (w1.udigit(size_w-1) + 1) +d = (UDIGIT_TYPE(MASK)+1) // (w1.udigit(abs(size_w-1)) + 1) assert d <= MASK# because the first digit of w1 is not zero d = longlongmask(d) v = _muladd1(v1, d) @@ -1535,9 +1535,9 @@ size_a = size_v - size_w + 1 a = rbigint([NULLDIGIT] * size_a, 1) -wm1 = w.widedigit(size_w-1) -wm2 = w.widedigit(size_w-2) -j = size_v +wm1 = w.widedigit(abs(size_w-1)) +
[pypy-commit] pypy improve-rbigint: Slight simplication. No performance
Author: stian Branch: improve-rbigint Changeset: r56346:f70dd5b364f0 Date: 2012-07-04 18:17 +0200 http://bitbucket.org/pypy/pypy/changeset/f70dd5b364f0/ Log:Slight simplication. No performance diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -1,4 +1,4 @@ -from pypy.rlib.rarithmetic import LONG_BIT, intmask, longlongmask, r_uint, r_int, r_ulonglong, r_longlonglong +from pypy.rlib.rarithmetic import LONG_BIT, intmask, longlongmask, r_uint, r_ulonglong, r_longlonglong from pypy.rlib.rarithmetic import ovfcheck, r_longlong, widen, is_valid_int from pypy.rlib.rarithmetic import most_neg_value_of_same_type from pypy.rlib.rfloat import isfinite @@ -32,11 +32,19 @@ BASE = long(1 << SHIFT) UDIGIT_TYPE = r_ulonglong UDIGIT_MASK = longlongmask +if LONG_BIT > SHIFT: +STORE_TYPE = lltype.Signed +UNSIGNED_TYPE = lltype.Unsigned +else: +STORE_TYPE = rffi.LONGLONG +UNSIGNED_TYPE = rffi.ULONGLONG else: SHIFT = 31 BASE = int(1 << SHIFT) UDIGIT_TYPE = r_uint UDIGIT_MASK = intmask +STORE_TYPE = lltype.Signed +UNSIGNED_TYPE = lltype.Unsigned MASK = BASE - 1 FLOAT_MULTIPLIER = float(1 << LONG_BIT) # Because it works. @@ -98,27 +106,15 @@ elif SHIFT <= 31: return rffi.cast(rffi.INT, x) elif SHIFT <= 63: -return rffi.cast(rffi.LONGLONG, x) +return rffi.cast(STORE_TYPE, x) else: raise ValueError("SHIFT too large!") _store_digit._annspecialcase_ = 'specialize:argtype(0)' _store_digit._always_inline_ = True -def _load_digit(x): -if SHIFT < LONG_BIT: # This would be the case for any SHIFT < LONG_BIT -return rffi.cast(lltype.Signed, x) -else: -# x already is a type large enough, just not as fast. -return x -_load_digit._always_inline_ = True - def _load_unsigned_digit(x): -if SHIFT < LONG_BIT: # This would be the case for any SHIFT < LONG_BIT -return rffi.cast(lltype.Unsigned, x) -else: -# This needs a performance test on 32bit -return rffi.cast(rffi.ULONGLONG, x) -#return r_ulonglong(x) +return rffi.cast(UNSIGNED_TYPE, x) + _load_unsigned_digit._always_inline_ = True NULLDIGIT = _store_digit(0) @@ -153,13 +149,13 @@ def digit(self, x): """Return the x'th digit, as an int.""" -return _load_digit(self._digits[x]) +return self._digits[x] digit._always_inline_ = True def widedigit(self, x): """Return the x'th digit, as a long long int if needed to have enough room to contain two digits.""" -return _widen_digit(_load_digit(self._digits[x])) +return _widen_digit(self._digits[x]) widedigit._always_inline_ = True def udigit(self, x): @@ -851,7 +847,6 @@ return "" % (self._digits, self.sign, self.str()) - ONERBIGINT = rbigint([ONEDIGIT], 1) NULLRBIGINT = rbigint() @@ -937,7 +932,7 @@ a, b = b, a size_a, size_b = size_b, size_a z = rbigint([NULLDIGIT] * (size_a + 1), 1) -i = _load_unsigned_digit(0) +i = UDIGIT_TYPE(0) carry = UDIGIT_TYPE(0) while i < size_b: carry += a.udigit(i) + b.udigit(i) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Improve the general speed of pow, special case 0 ** something and something ** 0, along with negative numbers.
Author: stian Branch: improve-rbigint Changeset: r56347:cd82209a05cb Date: 2012-07-05 20:23 +0200 http://bitbucket.org/pypy/pypy/changeset/cd82209a05cb/ Log:Improve the general speed of pow, special case 0 ** something and something ** 0, along with negative numbers. diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -558,6 +558,11 @@ # XXX failed to implement raise ValueError("bigint pow() too negative") +if b.sign == 0: +return ONERBIGINT +elif a.sign == 0: +return NULLRBIGINT + size_b = b.numdigits() if c is not None: @@ -574,7 +579,7 @@ # if modulus == 1: # return 0 if c.numdigits() == 1 and c.digit(0) == 1: -return rbigint() +return NULLRBIGINT # if base < 0: # base = base % modulus @@ -583,18 +588,23 @@ a = a.mod(c) -elif size_b == 1 and a.sign == 1: +elif size_b == 1: digit = b.digit(0) if digit == 0: -return ONERBIGINT +return ONERBIGINT if a.sign == 1 else ONENEGATIVERBIGINT elif digit == 1: return a elif a.numdigits() == 1: adigit = a.digit(0) if adigit == 1: +if a.sign == -1 and digit % 2: +return ONENEGATIVERBIGINT return ONERBIGINT elif adigit & (adigit - 1) == 0: -return a.lshift(((digit-1)*(ptwotable[adigit]-1)) + digit-1) +ret = a.lshift(((digit-1)*(ptwotable[adigit]-1)) + digit-1) +if a.sign == -1 and not digit % 2: +ret.sign = 1 +return ret # At this point a, b, and c are guaranteed non-negative UNLESS # c is NULL, in which case a may be negative. */ @@ -848,6 +858,7 @@ self.sign, self.str()) ONERBIGINT = rbigint([ONEDIGIT], 1) +ONENEGATIVERBIGINT = rbigint([ONEDIGIT], -1) NULLRBIGINT = rbigint() #_ diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -29,21 +29,21 @@ Sum: 901.723125001 Pypy with improvements: -2.884540 -2.499774 -3.796117 -1.681326 -4.060521 -9.696996 -1.643792 -4.045248 -4.714733 -6.589811 -0.039319 -3.503355 -8.266362 -5.044856 -Sum: 58.466750 +2.867820 +2.523047 +3.848003 +1.682992 +4.099669 +9.233212 +1.622695 +4.026895 +4.708891 +6.542558 +0.039864 +3.508814 +8.225711 +5.009382 +Sum: 57.939553 A pure python form of those tests where also run Improved pypy | Pypy | CPython 2.7.3 ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: A slight cleanup
Author: stian Branch: improve-rbigint Changeset: r56348:2fb65ab9c8ca Date: 2012-07-05 23:41 +0200 http://bitbucket.org/pypy/pypy/changeset/2fb65ab9c8ca/ Log:A slight cleanup diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -701,24 +701,21 @@ remshift = int_other - wordshift * SHIFT oldsize = self.numdigits() -newsize = oldsize + wordshift if not remshift: return rbigint([NULLDIGIT] * wordshift + self._digits, self.sign) -newsize += 1 - -z = rbigint([NULLDIGIT] * newsize, self.sign) +z = rbigint([NULLDIGIT] * (oldsize + wordshift + 1), self.sign) accum = _widen_digit(0) i = wordshift j = 0 while j < oldsize: -accum |= self.widedigit(j) << remshift +accum += self.widedigit(j) << remshift z.setdigit(i, accum) accum >>= SHIFT i += 1 j += 1 -z.setdigit(abs(newsize - 1), accum) +z.setdigit(oldsize, accum) z._normalize() return z ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Always inline _normalize. This give a HUGE speedup for lshift, but most calls that does very little work seem to benefit
Author: stian Branch: improve-rbigint Changeset: r56349:9be592831ad5 Date: 2012-07-06 04:49 +0200 http://bitbucket.org/pypy/pypy/changeset/9be592831ad5/ Log:Always inline _normalize. This give a HUGE speedup for lshift, but most calls that does very little work seem to benefit diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -831,7 +831,7 @@ self._digits = self._digits[:i] if self.numdigits() == 1 and self.udigit(0) == 0: self.sign = 0 - +_normalize._always_inline_ = True def bit_length(self): i = self.numdigits() if i == 1 and self.digit(0) == 0: @@ -1392,7 +1392,9 @@ if not size: size = pin.numdigits() size -= 1 + while size >= 0: +assert size >= 0 rem = (rem << SHIFT) + pin.widedigit(size) hi = rem // n pout.setdigit(size, hi) diff --git a/pypy/rpython/lltypesystem/rlist.py b/pypy/rpython/lltypesystem/rlist.py --- a/pypy/rpython/lltypesystem/rlist.py +++ b/pypy/rpython/lltypesystem/rlist.py @@ -303,12 +303,12 @@ return l.items def ll_getitem_fast(l, index): -ll_assert(index < l.length, "getitem out of bounds") +#ll_assert(index < l.length, "getitem out of bounds") return l.ll_items()[index] ll_getitem_fast.oopspec = 'list.getitem(l, index)' def ll_setitem_fast(l, index, item): -ll_assert(index < l.length, "setitem out of bounds") +#ll_assert(index < l.length, "setitem out of bounds") l.ll_items()[index] = item ll_setitem_fast.oopspec = 'list.setitem(l, index, item)' @@ -316,7 +316,7 @@ @typeMethod def ll_fixed_newlist(LIST, length): -ll_assert(length >= 0, "negative fixed list length") +#ll_assert(length >= 0, "negative fixed list length") l = malloc(LIST, length) return l ll_fixed_newlist.oopspec = 'newlist(length)' @@ -333,12 +333,12 @@ return l def ll_fixed_getitem_fast(l, index): -ll_assert(index < len(l), "fixed getitem out of bounds") +#ll_assert(index < len(l), "fixed getitem out of bounds") return l[index] ll_fixed_getitem_fast.oopspec = 'list.getitem(l, index)' def ll_fixed_setitem_fast(l, index, item): -ll_assert(index < len(l), "fixed setitem out of bounds") +#ll_assert(index < len(l), "fixed setitem out of bounds") l[index] = item ll_fixed_setitem_fast.oopspec = 'list.setitem(l, index, item)' ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Make a new normalize method that skips one check and post results 1.3s improvement, mostly on shifts
Author: stian Branch: improve-rbigint Changeset: r56350:eaaa4adb6819 Date: 2012-07-06 06:06 +0200 http://bitbucket.org/pypy/pypy/changeset/eaaa4adb6819/ Log:Make a new normalize method that skips one check and post results 1.3s improvement, mostly on shifts diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -717,7 +717,7 @@ z.setdigit(oldsize, accum) -z._normalize() +z._positivenormalize() return z lshift._always_inline_ = True # It's so fast that it's always benefitial. @@ -737,7 +737,7 @@ accum >>= SHIFT z.setdigit(oldsize, accum) -z._normalize() +z._positivenormalize() return z lqshift._always_inline_ = True # It's so fast that it's always benefitial. @@ -772,7 +772,7 @@ z.setdigit(i, newdigit) i += 1 j += 1 -z._normalize() +z._positivenormalize() return z rshift._always_inline_ = True # It's so fast that it's always benefitial. @@ -818,20 +818,34 @@ return l * self.sign def _normalize(self): -i = _load_unsigned_digit(self.numdigits()) +i = c = self.numdigits() if i == 0: self.sign = 0 self._digits = [NULLDIGIT] return -while i > 1 and self.udigit(i - 1) == 0: +while i > 1 and self.digit(i - 1) == 0: i -= 1 -assert i >= 1 -if i != self.numdigits(): +assert i > 0 +if i != c: self._digits = self._digits[:i] -if self.numdigits() == 1 and self.udigit(0) == 0: +if self.numdigits() == 1 and self.digit(0) == 0: self.sign = 0 + _normalize._always_inline_ = True + +def _positivenormalize(self): +""" This function assumes numdigits > 0. Good for shifts and such """ +i = c = self.numdigits() +while i > 1 and self.digit(i - 1) == 0: +i -= 1 +assert i > 0 +if i != c: +self._digits = self._digits[:i] +if self.numdigits() == 1 and self.digit(0) == 0: +self.sign = 0 +_positivenormalize._always_inline_ = True + def bit_length(self): i = self.numdigits() if i == 1 and self.digit(0) == 0: @@ -953,7 +967,7 @@ carry >>= SHIFT i += 1 z.setdigit(i, carry) -z._normalize() +z._positivenormalize() return z def _x_sub(a, b): @@ -1059,7 +1073,7 @@ z.setdigit(pz, z.widedigit(pz) + carry) assert (carry >> SHIFT) == 0 i += 1 -z._normalize() +z._positivenormalize() return z elif digit and digit & (digit - 1) == 0: @@ -1084,7 +1098,7 @@ z.setdigit(pz, z.widedigit(pz) + carry) assert (carry >> SHIFT) == 0 i += 1 -z._normalize() +z._positivenormalize() return z @@ -1190,8 +1204,8 @@ lo = rbigint(n._digits[:size_lo], 1) hi = rbigint(n._digits[size_lo:], 1) -lo._normalize() -hi._normalize() +lo._positivenormalize() +hi._positivenormalize() return hi, lo def _k_mul(a, b): @@ -1285,7 +1299,7 @@ # See the (*) comment after this function. _v_iadd(ret, shift, i, t3, t3.numdigits()) -ret._normalize() +ret._positivenormalize() return ret """ (*) Why adding t3 can't "run out of room" above. @@ -1379,7 +1393,7 @@ bsize -= nbtouse nbdone += nbtouse -ret._normalize() +ret._positivenormalize() return ret def _inplace_divrem1(pout, pin, n, size=0): diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -29,21 +29,21 @@ Sum: 901.723125001 Pypy with improvements: -2.867820 -2.523047 -3.848003 -1.682992 -4.099669 -9.233212 -1.622695 -4.026895 -4.708891 -6.542558 -0.039864 -3.508814 -8.225711 -5.009382 -Sum: 57.939553 +2.892875 +2.263349 +2.425365 +1.579653 +4.005316 +9.579625 +1.774452 +4.021076 +4.844961 +6.432300 +0.038368 +3.624531 +8.156838 +4.990594 +Sum: 56.629303 A pure python form of those tests where also run Improved pypy | Pypy | CPython 2.7.3 ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: More to the toom cook implantation, it's 'almost' correct. Added a failed test
Author: stian Branch: improve-rbigint Changeset: r56353:d8de5c59fe73 Date: 2012-07-06 22:41 +0200 http://bitbucket.org/pypy/pypy/changeset/d8de5c59fe73/ Log:More to the toom cook implantation, it's 'almost' correct. Added a failed test diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -454,7 +454,7 @@ if asize == 1: if a._digits[0] == NULLDIGIT: return rbigint() -elif b._digits[0] == ONEDIGIT: +elif a._digits[0] == ONEDIGIT: return rbigint(b._digits, a.sign * b.sign) elif bsize == 1: result = rbigint([NULLDIGIT] * 2, a.sign * b.sign) @@ -511,21 +511,7 @@ @jit.elidable def mod(self, other): -if other.numdigits() == 1: -# Faster. -i = 0 -mod = 0 -b = other.digit(0) * other.sign -while i < self.numdigits(): -digit = self.digit(i) * self.sign -if digit: -mod <<= SHIFT -mod = (mod + digit) % b - -i += 1 -mod = rbigint.fromint(mod) -else: -div, mod = _divrem(self, other) +div, mod = _divrem(self, other) if mod.sign * other.sign == -1: mod = mod.add(other) return mod @@ -1131,9 +1117,11 @@ viewing the shift as being by digits. The sign bit is ignored, and the return values are >= 0. """ -lo = rbigint(n._digits[:size], 1) -mid = rbigint(n._digits[size:size * 2], 1) -hi = rbigint(n._digits[size *2:], 1) +size_n = n.numdigits() / 3 +size_lo = min(size_n, size) +lo = rbigint(n._digits[:size_lo], 1) +mid = rbigint(n._digits[size_lo:size * 2], 1) +hi = rbigint(n._digits[size_lo *2:], 1) lo._normalize() mid._normalize() hi._normalize() @@ -1147,7 +1135,7 @@ bsize = b.numdigits() # Split a & b into hi, mid and lo pieces. -shift = asize // 3 +shift = bsize // 3 ah, am, al = _tcmul_split(a, shift) assert ah.sign == 1# the split isn't degenerate @@ -1158,46 +1146,39 @@ else: bh, bm, bl = _tcmul_split(b, shift) + # 1. Allocate result space. ret = rbigint([NULLDIGIT] * (asize + bsize), 1) -# 2. w points -pO = al.add(ah) -p1 = pO.add(am) -pn1 = pO.sub(am) -pn2 = pn1.add(ah).lshift(1).sub(al) +# 2. ahl, bhl +ahl = al.add(ah) +bhl = bl.add(bh) -qO = bl.add(bh) -q1 = qO.add(bm) -qn1 = qO.sub(bm) -qn2 = qn1.add(bh).lshift(1).sub(bl) +# Points +v0 = al.mul(bl) +v1 = ahl.add(bm).mul(bhl.add(bm)) -w0 = al.mul(bl) -winf = ah.mul(bh) - -w1 = p1.mul(q1) -wn1 = pn1.mul(qn1) -wn2 = pn2.mul(qn2) +vn1 = ahl.sub(bm).mul(bhl.sub(bm)) +v2 = al.add(am.lshift(1)).add(ah.lshift(2)).mul(bl.add(bm.lshift(1))).add(bh.lshift(2)) +vinf = ah.mul(bh) -# 3. The important stuff -# XXX: Need a faster / 3 and /2 like in GMP! -r0 = w0 -r4 = winf -r3 = _divrem1(wn2.sub(wn1), 3)[0] -r1 = w1.sub(wn1).rshift(1) -r2 = wn1.sub(w0) -r3 = _divrem1(r2.sub(r3), 2)[0].add(r4.lshift(1)) -r2 = r2.add(r1).sub(r4) -r1 = r1.sub(r3) +# Construct +t1 = v0.mul(rbigint.fromint(3)).add(vn1.lshift(1)).add(v2).floordiv(rbigint.fromint(6)).sub(vinf.lshift(1)) +t2 = v1.add(vn1).rshift(1) + +r1 = v1.sub(t1) +r2 = t2.sub(v0).sub(vinf) +r3 = t1.sub(t2) +# r0 = v0, r4 = vinf # Now we fit r+ r2 + r4 into the new string. # Now we got to add the r1 and r3 in the mid shift. This is TODO (aga, not fixed yet) -ret._digits[:shift] = r0._digits +ret._digits[:v0.numdigits()] = v0._digits -ret._digits[shift:shift*2] = r2._digits +ret._digits[shift * 2:shift * 2+r2.numdigits()] = r2._digits -ret._digits[shift*2:(shift*2)+r4.numdigits()] = r4._digits - +ret._digits[shift*4:shift*4+vinf.numdigits()] = vinf._digits + # TODO """ x and y are rbigints, m >= n required. x.digits[0:n] is modified in place, @@ -1205,8 +1186,8 @@ x[m-1], and the remaining carry (0 or 1) is returned. Python adaptation: x is addressed relative to xofs! """ -_v_iadd(ret, shift, shift + r1.numdigits(), r1, r1.numdigits()) -_v_iadd(ret, shift * 2, shift + r3.numdigits(), r3, r3.numdigits()) +_v_iadd(ret, shift, ret.numdigits() - shift * 4, r1, r1.numdigits()) +_v_iadd(ret, shift * 3, ret.numdigits() - shift * 4 , r3, r3.numdigits()) ret._normalize() return ret diff --git a/pypy/rlib/test/test_rbigint.py b/pypy/rlib/test/test_rbigint.py --- a/pypy/rlib/test/test_rbigint.py +++ b/pypy/rlib/test/test_rbigint.py @@ -3,7 +3,7 @@ import operator, sys, array from rando
[pypy-commit] pypy improve-rbigint: Working, but ineffective toom cook implantation
Author: stian Branch: improve-rbigint Changeset: r56354:62831f97a2c7 Date: 2012-07-07 00:50 +0200 http://bitbucket.org/pypy/pypy/changeset/62831f97a2c7/ Log:Working, but ineffective toom cook implantation diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -69,8 +69,8 @@ KARATSUBA_SQUARE_CUTOFF = 2 * KARATSUBA_CUTOFF -USE_TOOMCOCK = False # WIP -TOOMCOOK_CUTOFF = 3 # Smallest possible cutoff is 3. Ideal is probably around 150+ +USE_TOOMCOCK = False +TOOMCOOK_CUTOFF = 2000 # Smallest possible cutoff is 3. Ideal is probably around 150+ # For exponentiation, use the binary left-to-right algorithm # unless the exponent contains more than FIVEARY_CUTOFF digits. @@ -1127,6 +1127,7 @@ hi._normalize() return hi, mid, lo +THREERBIGINT = rbigint.fromint(3) # Used by tc_mul def _tc_mul(a, b): """ Toom Cook @@ -1145,11 +1146,6 @@ bl = al else: bh, bm, bl = _tcmul_split(b, shift) - - -# 1. Allocate result space. -ret = rbigint([NULLDIGIT] * (asize + bsize), 1) - # 2. ahl, bhl ahl = al.add(ah) bhl = bl.add(bh) @@ -1159,12 +1155,15 @@ v1 = ahl.add(bm).mul(bhl.add(bm)) vn1 = ahl.sub(bm).mul(bhl.sub(bm)) -v2 = al.add(am.lshift(1)).add(ah.lshift(2)).mul(bl.add(bm.lshift(1))).add(bh.lshift(2)) +v2 = al.add(am.lshift(1)).add(ah.lshift(2)).mul(bl.add(bm.lshift(1)).add(bh.lshift(2))) vinf = ah.mul(bh) # Construct -t1 = v0.mul(rbigint.fromint(3)).add(vn1.lshift(1)).add(v2).floordiv(rbigint.fromint(6)).sub(vinf.lshift(1)) -t2 = v1.add(vn1).rshift(1) +t1 = v0.mul(THREERBIGINT).add(vn1.lshift(1)).add(v2) +_inplace_divrem1(t1, t1, 6) +t1 = t1.sub(vinf.lshift(1)) +t2 = v1.add(vn1) +_v_rshift(t2, t2, t2.numdigits(), 1) r1 = v1.sub(t1) r2 = t2.sub(v0).sub(vinf) @@ -1172,24 +1171,29 @@ # r0 = v0, r4 = vinf # Now we fit r+ r2 + r4 into the new string. -# Now we got to add the r1 and r3 in the mid shift. This is TODO (aga, not fixed yet) +# Now we got to add the r1 and r3 in the mid shift. +# Allocate result space. +ret = rbigint([NULLDIGIT] * (4*shift + vinf.numdigits()), 1) # This is because of the size of vinf + ret._digits[:v0.numdigits()] = v0._digits - +#print ret.numdigits(), r2.numdigits(), vinf.numdigits(), shift, shift * 5, asize, bsize +#print r2.sign >= 0 +assert r2.sign >= 0 +#print 2*shift + r2.numdigits() < ret.numdigits() +assert 2*shift + r2.numdigits() < ret.numdigits() ret._digits[shift * 2:shift * 2+r2.numdigits()] = r2._digits - +#print vinf.sign >= 0 +assert vinf.sign >= 0 +#print 4*shift + vinf.numdigits() <= ret.numdigits() +assert 4*shift + vinf.numdigits() <= ret.numdigits() ret._digits[shift*4:shift*4+vinf.numdigits()] = vinf._digits -# TODO -""" -x and y are rbigints, m >= n required. x.digits[0:n] is modified in place, -by adding y.digits[0:m] to it. Carries are propagated as far as -x[m-1], and the remaining carry (0 or 1) is returned. -Python adaptation: x is addressed relative to xofs! -""" -_v_iadd(ret, shift, ret.numdigits() - shift * 4, r1, r1.numdigits()) -_v_iadd(ret, shift * 3, ret.numdigits() - shift * 4 , r3, r3.numdigits()) -ret._normalize() +i = ret.numdigits() - shift +_v_iadd(ret, shift, i, r1, r1.numdigits()) +_v_iadd(ret, shift * 3, i, r3, r3.numdigits()) + +ret._positivenormalize() return ret diff --git a/pypy/rlib/test/test_rbigint.py b/pypy/rlib/test/test_rbigint.py --- a/pypy/rlib/test/test_rbigint.py +++ b/pypy/rlib/test/test_rbigint.py @@ -459,6 +459,7 @@ def test_tc_mul(self): a = rbigint.fromlong(1<<300) b = rbigint.fromlong(1<<200) +print _tc_mul(a, b) assert _tc_mul(a, b).tolong() == ((1<<300)*(1<<200)) def test_overzelous_assertion(self): diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -64,6 +64,19 @@ """ sumTime = 0.0 + +t = time() +by = rbigint.pow(rbigint.fromint(63), rbigint.fromint(100)) +for n in xrange(9900): +by2 = by.lshift(63) +rbigint.mul(by, by2) +by = by2 + + +_time = time() - t +sumTime += _time +print "Toom-cook effectivity 100-1 digits:", _time + t = time() num = rbigint.pow(rbigint.fromint(1), rbigint.fromint(1024)) by = rbigint.pow(rbigint.fromint(2), rbigint.fromint(128)) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Reapply proofs of index >= 0 using unsigned (for mul this could in theory be done even quicker by making a unsigned longlonglong and avoid the cast)
Author: stian Branch: improve-rbigint Changeset: r56356:22b6be6db1ba Date: 2012-07-07 19:22 +0200 http://bitbucket.org/pypy/pypy/changeset/22b6be6db1ba/ Log:Reapply proofs of index >= 0 using unsigned (for mul this could in theory be done even quicker by making a unsigned longlonglong and avoid the cast) diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -1048,7 +1048,7 @@ # via exploiting that each entry in the multiplication # pyramid appears twice (except for the size_a squares). z = rbigint([NULLDIGIT] * (size_a + size_b), 1) -i = 0 +i = UDIGIT_TYPE(0) while i < size_a: f = a.widedigit(i) pz = i << 1 @@ -1071,12 +1071,7 @@ carry >>= SHIFT #assert carry <= (_widen_digit(MASK) << 1) if carry: -carry += z.widedigit(pz) -z.setdigit(pz, carry) -pz += 1 -carry >>= SHIFT -if carry: -z.setdigit(pz, z.widedigit(pz) + carry) +z.setdigit(pz, z.widedigit(pz) + carry) assert (carry >> SHIFT) == 0 i += 1 z._positivenormalize() @@ -1087,7 +1082,7 @@ z = rbigint([NULLDIGIT] * (size_a + size_b), 1) # gradeschool long mult -i = 0 +i = UDIGIT_TYPE(0) while i < size_a: carry = 0 f = a.widedigit(i) @@ -1565,9 +1560,9 @@ size_a = size_v - size_w + 1 a = rbigint([NULLDIGIT] * size_a, 1) -assert size_w >= 2 -wm1 = w.widedigit(size_w-1) -wm2 = w.widedigit(size_w-2) + +wm1 = w.widedigit(abs(size_w-1)) +wm2 = w.widedigit(abs(size_w-2)) j = size_v k = size_a - 1 while k >= 0: @@ -1578,7 +1573,7 @@ vj = v.widedigit(j) carry = 0 -vj1 = v.widedigit(j-1) +vj1 = v.widedigit(abs(j-1)) if vj == wm1: q = MASK @@ -1588,7 +1583,7 @@ q = vv // wm1 r = _widen_digit(vv) - wm1 * q -vj2 = v.widedigit(j-2) +vj2 = v.widedigit(abs(j-2)) while wm2 * q > ((r << SHIFT) | vj2): q -= 1 r += wm1 diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -29,21 +29,21 @@ Sum: 901.723125001 Pypy with improvements: -2.887265 -2.253981 -2.480497 -1.572440 -3.941691 -9.530685 -1.786801 -4.046154 -4.844644 -6.412511 -0.038662 -3.629173 -8.155449 -4.997199 -Sum: 56.577152 +2.885155 +2.301395 +2.425767 +1.526053 +4.066191 +9.405854 +1.622019 +3.089785 +4.844679 +6.211589 +0.038158 +3.629360 +8.194571 +5.65 +Sum: 55.240641 A pure python form of those tests where also run Improved pypy | Pypy | CPython 2.7.3 @@ -65,7 +65,7 @@ sumTime = 0.0 -t = time() +"""t = time() by = rbigint.pow(rbigint.fromint(63), rbigint.fromint(100)) for n in xrange(9900): by2 = by.lshift(63) @@ -75,7 +75,7 @@ _time = time() - t sumTime += _time -print "Toom-cook effectivity 100-1 digits:", _time +print "Toom-cook effectivity 100-1 digits:", _time""" t = time() num = rbigint.pow(rbigint.fromint(1), rbigint.fromint(1024)) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Use inplace_divrem to find the reminder from v, this makes divrem 20% faster
Author: stian Branch: improve-rbigint Changeset: r56358:6bb9597d48fc Date: 2012-07-07 21:13 +0200 http://bitbucket.org/pypy/pypy/changeset/6bb9597d48fc/ Log:Use inplace_divrem to find the reminder from v, this makes divrem 20% faster diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -1542,8 +1542,8 @@ d = longlongmask(d) v = _muladd1(v1, d) w = _muladd1(w1, d) -size_v = v1.numdigits() -size_w = w1.numdigits() +size_v = v.numdigits() +size_w = w.numdigits() assert size_v >= size_w and size_w > 1 # (Assert checks by div() """v = rbigint([NULLDIGIT] * (size_v + 1)) @@ -1622,8 +1622,8 @@ k -= 1 a._normalize() -rem, _ = _divrem1(v, d) -return a, rem +_inplace_divrem1(v, v, d, size_v) +return a, v """ Didn't work as expected. Someone want to look over this? diff --git a/pypy/rlib/test/test_rbigint.py b/pypy/rlib/test/test_rbigint.py --- a/pypy/rlib/test/test_rbigint.py +++ b/pypy/rlib/test/test_rbigint.py @@ -535,7 +535,9 @@ f1 = rbigint.fromlong(x) f2 = rbigint.fromlong(y) div, rem = lobj._x_divrem(f1, f2) -assert div.tolong(), rem.tolong() == divmod(x, y) +_div, _rem = divmod(x, y) +print div.tolong() == _div +print rem.tolong() == _rem def test__divrem(self): x = 12345678901234567890L @@ -549,7 +551,9 @@ f1 = rbigint.fromlong(sx) f2 = rbigint.fromlong(sy) div, rem = lobj._x_divrem(f1, f2) -assert div.tolong(), rem.tolong() == divmod(sx, sy) +_div, _rem = divmod(sx, sy) +print div.tolong() == _div +print rem.tolong() == _rem # testing Karatsuba stuff def test__v_iadd(self): diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -29,21 +29,21 @@ Sum: 901.723125001 Pypy with improvements: -2.873703 -2.154623 -2.427906 -1.458865 -4.101600 -9.396741 -1.613343 -3.073679 -4.862458 -6.202641 -0.038174 -3.642065 -8.126947 -5.075265 -Sum: 55.048011 +2.156113 +2.139545 +2.413156 +1.496088 +4.047559 +9.551884 +1.625509 +3.048558 +4.867547 +6.223230 +0.038463 +3.637759 +8.325080 +5.038974 +Sum: 54.609465 A pure python form of those tests where also run Improved pypy | Pypy | CPython 2.7.3 ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: New results
Author: stian Branch: improve-rbigint Changeset: r56360:e14a09f12678 Date: 2012-07-08 00:24 +0200 http://bitbucket.org/pypy/pypy/changeset/e14a09f12678/ Log:New results diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -10,43 +10,49 @@ """ All benchmarks are run using --opt=2 and minimark gc (default). +Benchmark changes: +2**N is a VERY heavy operation in default pypy, default to 10 million instead of 500,000 used like an hour to finish. + A cutout with some benchmarks. Pypy default: -2.803071 -2.366586 -2.428205 -4.408400 -4.424533 -537.338 -268.3339 -8.548186 -12.197392 -17.629869 -2.360716 -14.315827 -17.963899 -6.604541 -Sum: 901.723125001 +mod by 2: 7.978181 +mod by 1: 4.016121 +mod by 1024 (power of two): 3.966439 +Div huge number by 2**128: 2.906821 +rshift: 2.444589 +lshift: 2.500746 +Floordiv by 2: 4.431134 +Floordiv by 3 (not power of two): 4.404396 +2**50: 23.206724 +(2**N)**500 (power of two): 13.886118 +1 ** BIGNUM % 100 8.464378 +i = i * i: 10.121505 +n**1 (not power of two): 16.296989 +Power of two ** power of two: 2.224125 +v = v * power of two 12.228391 +v = v * v 17.119933 +v = v + v 6.489957 +Sum: 142.686547 Pypy with improvements: -mod by 2: 0.006297 -mod by 1: 3.693501 -mod by 1024 (power of two): 0.011243 -Div huge number by 2**128: 2.163590 -rshift: 2.219846 -lshift: 2.689848 -Floordiv by 2: 1.460396 -Floordiv by 3 (not power of two): 4.071267 -2**1000: 9.720923 -(2**N)**1 (power of two): 1.639600 -1 ** BIGNUM % 100 1.738285 -i = i * i: 4.861456 -n**1 (not power of two): 6.206040 -Power of two ** power of two: 0.038726 -v = v * power of two 3.633579 -v = v * v 8.180117 -v = v + v 5.006874 -Sum: 57.341588 +mod by 2: 0.007535 +mod by 1: 3.686409 +mod by 1024 (power of two): 0.011153 +Div huge number by 2**128: 2.162245 +rshift: 2.211261 +lshift: 2.711231 +Floordiv by 2: 1.481641 +Floordiv by 3 (not power of two): 4.067045 +2**50: 0.155143 +(2**N)**500 (power of two): 0.098826 +1 ** BIGNUM % 100 1.742109 +i = i * i: 4.836238 +n**1 (not power of two): 6.196422 +Power of two ** power of two: 0.038207 +v = v * power of two 3.629006 +v = v * v 8.220768 +v = v + v 4.998141 +Sum: 46.253380 A pure python form of those tests where also run Improved pypy | Pypy | CPython 2.7.3 @@ -161,24 +167,24 @@ print "Floordiv by 3 (not power of two):",_time t = time() -num = rbigint.fromint(1000) +num = rbigint.fromint(50) for n in xrange(1): rbigint.pow(V2, num) _time = time() - t sumTime += _time -print "2**1000:",_time +print "2**50:",_time t = time() -num = rbigint.fromint(1) +num = rbigint.fromint(500) for n in xrange(31): rbigint.pow(rbigint.pow(V2, rbigint.fromint(n)), num) _time = time() - t sumTime += _time -print "(2**N)**1 (power of two):",_time +print "(2**N)**500 (power of two):",_time t = time() num = rbigint.pow(rbigint.fromint(1), rbigint.fromint(2 ** 8)) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Vast improvement, especially to add and mul by self
Author: stian Branch: improve-rbigint Changeset: r56361:4ffb2cad4eaa Date: 2012-07-12 17:47 +0200 http://bitbucket.org/pypy/pypy/changeset/4ffb2cad4eaa/ Log:Vast improvement, especially to add and mul by self diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -145,6 +145,7 @@ _check_digits(digits) make_sure_not_resized(digits) self._digits = digits +self.size = len(digits) self.sign = sign def digit(self, x): @@ -172,7 +173,7 @@ setdigit._always_inline_ = True def numdigits(self): -return len(self._digits) +return self.size numdigits._always_inline_ = True @staticmethod @@ -755,7 +756,7 @@ assert newsize >= 0 z.setdigit(newsize, accum) -z._positivenormalize() +z._normalize() return z lshift._always_inline_ = True # It's so fast that it's always benefitial. @@ -775,7 +776,7 @@ accum >>= SHIFT z.setdigit(oldsize, accum) -z._positivenormalize() +z._normalize() return z lqshift._always_inline_ = True # It's so fast that it's always benefitial. @@ -810,7 +811,7 @@ z.setdigit(i, newdigit) i += 1 wordshift += 1 -z._positivenormalize() +z._normalize() return z rshift._always_inline_ = True # It's so fast that it's always benefitial. @@ -859,6 +860,7 @@ i = c = self.numdigits() if i == 0: self.sign = 0 +self.size = 1 self._digits = [NULLDIGIT] return @@ -866,23 +868,12 @@ i -= 1 assert i > 0 if i != c: -self._digits = self._digits[:i] +self.size = i if self.numdigits() == 1 and self._digits[0] == NULLDIGIT: self.sign = 0 +self._digits = [NULLDIGIT] -#_normalize._always_inline_ = True - -def _positivenormalize(self): -""" This function assumes numdigits > 0. Good for shifts and such """ -i = c = self.numdigits() -while i > 1 and self._digits[i - 1] == NULLDIGIT: -i -= 1 -assert i > 0 -if i != c: -self._digits = self._digits[:i] -if self.numdigits() == 1 and self._digits[0] == NULLDIGIT: -self.sign = 0 -_positivenormalize._always_inline_ = True +_normalize._always_inline_ = True def bit_length(self): i = self.numdigits() @@ -1005,7 +996,7 @@ carry >>= SHIFT i += 1 z.setdigit(i, carry) -z._positivenormalize() +z._normalize() return z def _x_sub(a, b): @@ -1105,7 +1096,7 @@ z.setdigit(pz, z.widedigit(pz) + carry) assert (carry >> SHIFT) == 0 i += 1 -z._positivenormalize() +z._normalize() return z elif digit and digit & (digit - 1) == 0: @@ -1131,7 +1122,7 @@ z.setdigit(pz, z.widedigit(pz) + carry) assert (carry >> SHIFT) == 0 i += 1 -z._positivenormalize() +z._normalize() return z @@ -1219,7 +1210,7 @@ _v_iadd(ret, shift, i, r1, r1.numdigits()) _v_iadd(ret, shift * 3, i, r3, r3.numdigits()) -ret._positivenormalize() +ret._normalize() return ret @@ -1236,8 +1227,8 @@ lo = rbigint(n._digits[:size_lo], 1) hi = rbigint(n._digits[size_lo:], 1) -lo._positivenormalize() -hi._positivenormalize() +lo._normalize() +hi._normalize() return hi, lo def _k_mul(a, b): @@ -1331,7 +1322,7 @@ # See the (*) comment after this function. _v_iadd(ret, shift, i, t3, t3.numdigits()) -ret._positivenormalize() +ret._normalize() return ret """ (*) Why adding t3 can't "run out of room" above. @@ -1425,7 +1416,7 @@ bsize -= nbtouse nbdone += nbtouse -ret._positivenormalize() +ret._normalize() return ret def _inplace_divrem1(pout, pin, n, size=0): diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -35,24 +35,24 @@ Sum: 142.686547 Pypy with improvements: -mod by 2: 0.007535 -mod by 1: 3.686409 -mod by 1024 (power of two): 0.011153 -Div huge number by 2**128: 2.162245 -rshift: 2.211261 -lshift: 2.711231 -Floordiv by 2: 1.481641 -Floordiv by 3 (not power of two): 4.067045 -2**50: 0.155143 -(2**N)**500 (power of two): 0.098826 -1 ** BIGNUM % 100 1.742109 -i = i * i:
[pypy-commit] pypy improve-rbigint: Probably my final toom cook test. Didn't go so well. Also disable jit.eldible because it seems to slow down good algoritms
Author: stian Branch: improve-rbigint Changeset: r56362:fd2621060fe3 Date: 2012-07-12 19:38 +0200 http://bitbucket.org/pypy/pypy/changeset/fd2621060fe3/ Log:Probably my final toom cook test. Didn't go so well. Also disable jit.eldible because it seems to slow down good algoritms diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -70,7 +70,7 @@ KARATSUBA_SQUARE_CUTOFF = 2 * KARATSUBA_CUTOFF USE_TOOMCOCK = False -TOOMCOOK_CUTOFF = 2000 # Smallest possible cutoff is 3. Ideal is probably around 150+ +TOOMCOOK_CUTOFF = 1 # Smallest possible cutoff is 3. Ideal is probably around 150+ # For exponentiation, use the binary left-to-right algorithm # unless the exponent contains more than FIVEARY_CUTOFF digits. @@ -220,7 +220,7 @@ return v @staticmethod -@jit.elidable +#@jit.elidable def frombool(b): # This function is marked as pure, so you must not call it and # then modify the result. @@ -335,21 +335,21 @@ def tofloat(self): return _AsDouble(self) -@jit.elidable +#@jit.elidable def format(self, digits, prefix='', suffix=''): # 'digits' is a string whose length is the base to use, # and where each character is the corresponding digit. return _format(self, digits, prefix, suffix) -@jit.elidable +#@jit.elidable def repr(self): return _format(self, BASE10, '', 'L') -@jit.elidable +#@jit.elidable def str(self): return _format(self, BASE10) -@jit.elidable +#@jit.elidable def eq(self, other): if (self.sign != other.sign or self.numdigits() != other.numdigits()): @@ -365,7 +365,7 @@ def ne(self, other): return not self.eq(other) -@jit.elidable +#@jit.elidable def lt(self, other): if self.sign > other.sign: return False @@ -413,7 +413,7 @@ def hash(self): return _hash(self) -@jit.elidable +#@jit.elidable def add(self, other): if self.sign == 0: return other @@ -426,7 +426,7 @@ result.sign *= other.sign return result -@jit.elidable +#@jit.elidable def sub(self, other): if other.sign == 0: return self @@ -439,7 +439,7 @@ result.sign *= self.sign return result -@jit.elidable +#@jit.elidable def mul(self, b): asize = self.numdigits() bsize = b.numdigits() @@ -487,12 +487,12 @@ result.sign = a.sign * b.sign return result -@jit.elidable +#@jit.elidable def truediv(self, other): div = _bigint_true_divide(self, other) return div -@jit.elidable +#@jit.elidable def floordiv(self, other): if other.numdigits() == 1 and other.sign == 1: digit = other.digit(0) @@ -506,11 +506,11 @@ div = div.sub(ONERBIGINT) return div -@jit.elidable +#@jit.elidable def div(self, other): return self.floordiv(other) -@jit.elidable +#@jit.elidable def mod(self, other): if self.sign == 0: return NULLRBIGINT @@ -549,7 +549,7 @@ mod = mod.add(other) return mod -@jit.elidable +#@jit.elidable def divmod(v, w): """ The / and % operators are now defined in terms of divmod(). @@ -573,7 +573,7 @@ div = div.sub(ONERBIGINT) return div, mod -@jit.elidable +#@jit.elidable def pow(a, b, c=None): negativeOutput = False # if x<0 return negative output @@ -726,7 +726,7 @@ ret.sign = -ret.sign return ret -@jit.elidable +#@jit.elidable def lshift(self, int_other): if int_other < 0: raise ValueError("negative shift count") @@ -760,7 +760,7 @@ return z lshift._always_inline_ = True # It's so fast that it's always benefitial. -@jit.elidable +#@jit.elidable def lqshift(self, int_other): " A quicker one with much less checks, int_other is valid and for the most part constant." assert int_other > 0 @@ -780,7 +780,7 @@ return z lqshift._always_inline_ = True # It's so fast that it's always benefitial. -@jit.elidable +#@jit.elidable def rshift(self, int_other, dont_invert=False): if int_other < 0: raise ValueError("negative shift count") @@ -815,15 +815,15 @@ return z rshift._always_inline_ = True # It's so fast that it's always benefitial. -@jit.elidable +#@jit.elidable def and_(self, other): return _bitwise(self, '&', other) -@jit.elidable +#@jit.elidable def
[pypy-commit] pypy improve-rbigint: Remove elidable from a few calls.
Author: stian Branch: improve-rbigint Changeset: r56367:9b64f64a53a6 Date: 2012-07-14 01:47 +0200 http://bitbucket.org/pypy/pypy/changeset/9b64f64a53a6/ Log:Remove elidable from a few calls. diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -318,16 +318,13 @@ raise ValueError("cannot convert negative integer to unsigned int") return _AsULonglong_ignore_sign(self) -@jit.elidable def uintmask(self): return _AsUInt_mask(self) -@jit.elidable def ulonglongmask(self): """Return r_ulonglong(self), truncating.""" return _AsULonglong_mask(self) -@jit.elidable def tofloat(self): return _AsDouble(self) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Fix a tiny issue when SUPPORT_INT = False, also add benchmark results
Author: stian Branch: improve-rbigint Changeset: r56368:e372c50f3914 Date: 2012-07-14 02:41 +0200 http://bitbucket.org/pypy/pypy/changeset/e372c50f3914/ Log:Fix a tiny issue when SUPPORT_INT = False, also add benchmark results diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -90,19 +90,10 @@ else: return r_longlong(x) _widen_digit._always_inline_ = True + def _store_digit(x): -"""if not we_are_translated(): -assert is_valid_int(x), "store_digit() takes an int, got a %r" % type(x)""" -if SHIFT <= 15: -return rffi.cast(rffi.SHORT, x) -elif SHIFT <= 31: -return rffi.cast(rffi.INT, x) -elif SHIFT <= 63: -return rffi.cast(STORE_TYPE, x) -else: -raise ValueError("SHIFT too large!") +return rffi.cast(STORE_TYPE, x) _store_digit._annspecialcase_ = 'specialize:argtype(0)' -_store_digit._always_inline_ = True def _load_unsigned_digit(x): return rffi.cast(UNSIGNED_TYPE, x) diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -54,22 +54,27 @@ v = v + v 2.820538 Sum: 41.234060 -A pure python form of those tests where also run -Improved pypy | Pypy | CPython 2.7.3 -0.0002100467681882.82172012329 1.38699007034 -0.123202085495 0.1261301040658.17586708069 -0.123197078705 0.1243581771858.34655714035 -0.0616521835327 0.0626962184906 4.88309693336 -0.0617570877075 0.0626759529114 4.88519001007 -0.000902891159058479.282402992 (forever, I yet it run for 5min before quiting) -1.65824794769(forever) (another forever) -0.0001978874206546.59566307068 8.29050803185 -5.3259730339112.1487128735 7.1309800148 -6.4518270492615.0498359203 11.733394146 -0.0001199245452882.13657021523 1.67227101326 -3.9634640216814.7546520233 9.05311799049 -8.3048419952417.0125601292 11.1488289833 -4.999716997156.59027791023 3.63601899147 + +With SUPPORT_INT128 set to False +mod by 2: 0.004103 +mod by 1: 3.237434 +mod by 1024 (power of two): 0.016363 +Div huge number by 2**128: 2.836237 +rshift: 2.343860 +lshift: 1.172665 +Floordiv by 2: 1.537474 +Floordiv by 3 (not power of two): 3.796015 +2**50: 0.327269 +(2**N)**500 (power of two): 0.084709 +1 ** BIGNUM % 100 2.063215 +i = i * i: 8.109634 +n**1 (not power of two): 11.243292 +Power of two ** power of two: 0.072559 +v = v * power of two 9.753532 +v = v * v 13.569841 +v = v + v 5.760466 +Sum: 65.928667 + """ sumTime = 0.0 ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Fix for passing divrem tests on 32bit.
Author: stian Branch: improve-rbigint Changeset: r56370:21926aa23a98 Date: 2012-07-14 21:20 +0200 http://bitbucket.org/pypy/pypy/changeset/21926aa23a98/ Log:Fix for passing divrem tests on 32bit. diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -76,13 +76,8 @@ FIVEARY_CUTOFF = 8 -if SHIFT <= 31: -def _mask_digit(x): -return intmask(x & MASK) -else: -def _mask_digit(x): -return longlongmask(x & MASK) - +def _mask_digit(x): +return UDIGIT_MASK(x & MASK) _mask_digit._annspecialcase_ = 'specialize:argtype(0)' def _widen_digit(x): @@ -103,10 +98,7 @@ def _check_digits(l): for x in l: assert type(x) is type(NULLDIGIT) -if SHIFT <= 31: -assert intmask(x) & MASK == intmask(x) -else: -assert longlongmask(x) & MASK == longlongmask(x) +assert UDIGIT_MASK(x) & MASK == UDIGIT_MASK(x) class Entry(extregistry.ExtRegistryEntry): _about_ = _check_digits @@ -1564,12 +1556,12 @@ size_w = w1.numdigits() d = (UDIGIT_TYPE(MASK)+1) // (w1.udigit(abs(size_w-1)) + 1) assert d <= MASK# because the first digit of w1 is not zero -d = longlongmask(d) +d = UDIGIT_MASK(d) v = _muladd1(v1, d) w = _muladd1(w1, d) size_v = v.numdigits() size_w = w.numdigits() -assert size_v >= size_w and size_w > 1 # (Assert checks by div() +assert size_w > 1 # (Assert checks by div() """v = rbigint([NULLDIGIT] * (size_v + 1)) w = rbigint([NULLDIGIT] * (size_w)) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Make a branch to improve rbigint
Author: stian Branch: improve-rbigint Changeset: r56308:5b013f1875b8 Date: 2012-06-21 22:14 +0200 http://bitbucket.org/pypy/pypy/changeset/5b013f1875b8/ Log:Make a branch to improve rbigint ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Unnecessary code removal
Author: stian Branch: improve-rbigint Changeset: r56313:a9b44897cc6b Date: 2012-06-22 02:26 +0200 http://bitbucket.org/pypy/pypy/changeset/a9b44897cc6b/ Log:Unnecessary code removal diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -979,10 +979,6 @@ return rbigint() # zero else: return _x_mul(a, b) - -if asize == 1: -# Then _x_mul will always be faster. -return _x_mul(a, b) # If a is small compared to b, splitting on b gives a degenerate # case with ah==0, and Karatsuba may be (even much) less efficient ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Add special cases for 0, 1 and power of two multiplication.
Author: stian Branch: improve-rbigint Changeset: r56311:0624736de0b2 Date: 2012-06-22 01:09 +0200 http://bitbucket.org/pypy/pypy/changeset/0624736de0b2/ Log:Add special cases for 0, 1 and power of two multiplication. Increase both general multiplications like this: for n in xrange(1): rbigint.pow(rbigint.fromint(n), rbigint.fromint(10**4)) And: for n in xrange(10): rbigint.pow(rbigint.fromint(1024), rbigint.fromint(1024)) By 6-7%. diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -789,6 +789,7 @@ sign = -1 a, b = b, a size_a = size_b = i+1 + z = rbigint([NULLDIGIT] * size_a, sign) borrow = r_uint(0) i = 0 @@ -810,7 +811,12 @@ z._normalize() return z - +# A neat little table of power of twos. +ptwotable = {} +for x in range(SHIFT): +ptwotable[2 << x] = x+1 +ptwotable[-2 << x] = x+1 + def _x_mul(a, b): """ Grade school multiplication, ignoring the signs. @@ -819,7 +825,6 @@ size_a = a.numdigits() size_b = b.numdigits() -z = rbigint([NULLDIGIT] * (size_a + size_b), 1) """ # Code below actually runs slower (about 20%). Dunno why, since it shouldn't. if a is b: @@ -861,6 +866,17 @@ assert (carry >> SHIFT) == 0 i += 1 else:""" +if size_a == 1: +# Special case. +digit = a.digit(0) +if digit == 0: +return rbigint(a._digits[:], 1) +elif digit == 1: +return rbigint(b._digits[:], 1) +elif digit & (digit - 1) == 0: +return b.lshift(ptwotable[digit]) + +z = rbigint([NULLDIGIT] * (size_a + size_b), 1) # gradeschool long mult i = 0 while i < size_a: @@ -931,6 +947,10 @@ else: return _x_mul(a, b) +if asize == 1: +# Then _x_mul will always be faster. +return _x_mul(a, b) + # If a is small compared to b, splitting on b gives a degenerate # case with ah==0, and Karatsuba may be (even much) less efficient # than "grade school" then. However, we can still win, by viewing @@ -1135,6 +1155,7 @@ The sign of a is ignored; n should not be zero. """ assert n > 0 and n <= MASK + size = a.numdigits() z = rbigint([NULLDIGIT] * size, 1) rem = _inplace_divrem1(z, a, n) @@ -1198,6 +1219,11 @@ def _muladd1(a, n, extra=0): """Multiply by a single digit and add a single digit, ignoring the sign. """ + +# Special case this one. +if n == 1 and not extra: +return a + size_a = a.numdigits() z = rbigint([NULLDIGIT] * (size_a+1), 1) assert extra & MASK == extra ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Fix a test and add some benchmarks for pow, mul and add operations.
Author: stian Branch: improve-rbigint Changeset: r56316:9fef3c53 Date: 2012-06-22 03:54 +0200 http://bitbucket.org/pypy/pypy/changeset/9fef3c53/ Log:Fix a test and add some benchmarks for pow, mul and add operations. diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -864,7 +864,7 @@ if digit == 0: return rbigint([NULLDIGIT], 1) elif digit == 1: -return rbigint([b._digits[0]], 1) +return rbigint(b._digits[:], 1) size_b = b.numdigits() diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py new file mode 100644 --- /dev/null +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -0,0 +1,78 @@ +#! /usr/bin/env python + +import os, sys +from time import time +from pypy.rlib.rbigint import rbigint + +# __ Entry point __ + +def entry_point(argv): +""" +A cutout with some benchmarks. +Pypy default: +18.270045 +2.512140 +14.148920 +18.576713 +6.647562 + +Pypy with improvements: +15.211410 +1.707288 +13.955348 +14.474590 +6.446812 + +""" +t = time() + +for n in xrange(1): +rbigint.pow(rbigint.fromint(n), rbigint.fromint(10**4)) + + +print time() - t + +t = time() + +for n in xrange(10): +rbigint.pow(rbigint.fromint(1024), rbigint.fromint(1024)) + + +print time() - t + + +t = time() +v = rbigint.fromint(2) +for n in xrange(5): +v = v.mul(rbigint.fromint(2**62)) + + +print time() - t + +t = time() +v2 = rbigint.fromint(2**8) +for n in xrange(28): +v2 = v2.mul(v2) + + +print time() - t + +t = time() +v3 = rbigint.fromint(2**62) +for n in xrange(50): +v3 = v3.add(v3) + + +print time() - t + +return 0 + +# _ Define and setup target ___ + +def target(*args): +return entry_point, None + +if __name__ == '__main__': +import sys +res = entry_point(sys.argv) +sys.exit(res) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: More optimalization and a bug fix.
Author: stian Branch: improve-rbigint Changeset: r56312:0b802b5f307e Date: 2012-06-22 02:16 +0200 http://bitbucket.org/pypy/pypy/changeset/0b802b5f307e/ Log:More optimalization and a bug fix. Revert _normalize() it causes a test to fail when _x_sub is special cased. Add special cases to _x_add, _x_sub Add a lqshift function for those more constant shifts. It's slightly quicker. Add operations benchmarked to 4% improvement in general. diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -561,6 +561,26 @@ z._normalize() return z +def lqshift(self, int_other): +" A quicker one with much less checks, int_other is valid and for the most part constant." +if int_other == 0: +return self + +oldsize = self.numdigits() +newsize = oldsize + 1 + +z = rbigint([NULLDIGIT] * newsize, self.sign) +accum = _widen_digit(0) + +for i in range(oldsize): +accum += self.widedigit(i) << int_other +z.setdigit(i, accum) +accum >>= SHIFT + +z.setdigit(newsize - 1, accum) +z._normalize() +return z + def rshift(self, int_other, dont_invert=False): if int_other < 0: raise ValueError("negative shift count") @@ -642,8 +662,8 @@ assert i >= 1 if i != self.numdigits(): self._digits = self._digits[:i] -if self.numdigits() == 1 and self.digit(0) == 0: -self.sign = 0 +if self.numdigits() == 1 and self.digit(0) == 0: +self.sign = 0 def bit_length(self): i = self.numdigits() @@ -743,7 +763,15 @@ def _x_add(a, b): """ Add the absolute values of two bigint integers. """ + size_a = a.numdigits() + +# Special casing. This is good, sometimes. +# The sweetspot is hard to find. But it's someplace between 60 and 70. +if size_a < 65 and a is b: +return a.lqshift(1) + + size_b = b.numdigits() # Ensure a is the larger of the two: @@ -769,6 +797,11 @@ def _x_sub(a, b): """ Subtract the absolute values of two integers. """ + +# Special casing. +if a is b: +return rbigint([NULLDIGIT], 1) + size_a = a.numdigits() size_b = b.numdigits() sign = 1 @@ -870,11 +903,11 @@ # Special case. digit = a.digit(0) if digit == 0: -return rbigint(a._digits[:], 1) +return rbigint([NULLDIGIT], 1) elif digit == 1: return rbigint(b._digits[:], 1) elif digit & (digit - 1) == 0: -return b.lshift(ptwotable[digit]) +return b.lqshift(ptwotable[digit]) z = rbigint([NULLDIGIT] * (size_a + size_b), 1) # gradeschool long mult ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Add another benchmark
Author: stian Branch: improve-rbigint Changeset: r56317:dfdf90fd7a0f Date: 2012-06-22 20:16 +0200 http://bitbucket.org/pypy/pypy/changeset/dfdf90fd7a0f/ Log:Add another benchmark diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -24,6 +24,15 @@ 6.446812 """ + +t = time() +i = rbigint.fromint(2**31) +i2 = rbigint.fromint(2**31) +for n in xrange(75000): +i = i.mul(i2) + +print time() - t + t = time() for n in xrange(1): ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Remove the special casing in _x_add, it's really the same (only that by doing this, we also got to do two extra checks, which makes it slower)
Author: stian Branch: improve-rbigint Changeset: r56319:e23369402d82 Date: 2012-06-23 00:41 +0200 http://bitbucket.org/pypy/pypy/changeset/e23369402d82/ Log:Remove the special casing in _x_add, it's really the same (only that by doing this, we also got to do two extra checks, which makes it slower) diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -763,20 +763,13 @@ """ Add the absolute values of two bigint integers. """ size_a = a.numdigits() - -# Special casing. This is good, sometimes. -# The sweetspot is hard to find. But it's someplace between 60 and 70. -if size_a < 65 and a is b: -return a.lqshift(1) - - size_b = b.numdigits() # Ensure a is the larger of the two: if size_a < size_b: a, b = b, a size_a, size_b = size_b, size_a -z = rbigint([NULLDIGIT] * (a.numdigits() + 1), 1) +z = rbigint([NULLDIGIT] * (size_a + 1), 1) i = 0 carry = r_uint(0) while i < size_b: diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -10,7 +10,8 @@ """ A cutout with some benchmarks. Pypy default: - +8.637287 +12.211942 18.270045 2.512140 14.148920 @@ -24,7 +25,7 @@ 1.635417 12.023154 14.320596 -6.464143 +6.439088 """ ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Reorganize to make room for toom cock (WIP)
Author: stian Branch: improve-rbigint Changeset: r56320:398e2b212e8b Date: 2012-06-23 05:15 +0200 http://bitbucket.org/pypy/pypy/changeset/398e2b212e8b/ Log:Reorganize to make room for toom cock (WIP) This also gave the first pow(a,b,c) benchmark a boost. Perhaps since some tricks kicks in earlier diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -36,6 +36,8 @@ KARATSUBA_CUTOFF = 38 KARATSUBA_SQUARE_CUTOFF = 2 * KARATSUBA_CUTOFF +USE_TOOMCOCK = False +TOOMCOOK_CUTOFF = 102 # For exponentiation, use the binary left-to-right algorithm # unless the exponent contains more than FIVEARY_CUTOFF digits. @@ -365,12 +367,44 @@ result._normalize() return result -def mul(self, other): -if USE_KARATSUBA: -result = _k_mul(self, other) +def mul(self, b): +asize = self.numdigits() +bsize = b.numdigits() + +a = self + +if asize > bsize: +a, b, asize, bsize = b, a, bsize, asize + +if a.sign == 0 or b.sign == 0: +return rbigint() + +if asize == 1: +digit = a.digit(0) +if digit == 0: +return rbigint() +elif digit == 1: +return rbigint(b._digits[:], a.sign * b.sign) + +result = _x_mul(a, b, digit) +elif USE_TOOMCOCK and asize >= TOOMCOOK_CUTOFF: +result = _tc_mul(a, b) +elif USE_KARATSUBA: +if a is b: +i = KARATSUBA_SQUARE_CUTOFF +else: +i = KARATSUBA_CUTOFF + +if asize <= i: +result = _x_mul(a, b) +elif 2 * asize <= bsize: +result = _k_lopsided_mul(a, b) +else: +result = _k_mul(a, b) else: -result = _x_mul(self, other) -result.sign = self.sign * other.sign +result = _x_mul(a, b) + +result.sign = a.sign * b.sign return result def truediv(self, other): @@ -848,15 +882,6 @@ """ size_a = a.numdigits() - -if size_a == 1: -# Special case. -digit = a.digit(0) -if digit == 0: -return rbigint([NULLDIGIT], 1) -elif digit == 1: -return rbigint(b._digits[:], 1) # We assume b was normalized already. - size_b = b.numdigits() if a is b: @@ -927,6 +952,103 @@ return z +def _tcmul_split(n, size): +""" +A helper for Karatsuba multiplication (k_mul). +Takes a bigint "n" and an integer "size" representing the place to +split, and sets low and high such that abs(n) == (high << size) + low, +viewing the shift as being by digits. The sign bit is ignored, and +the return values are >= 0. +""" + +assert size > 0 + +size_n = n.numdigits() +shift = min(size_n, size) + +lo = rbigint(n._digits[:shift], 1) +if size_n >= (shift * 2): +mid = rbigint(n._digits[shift:shift >> 1], 1) +hi = rbigint(n._digits[shift >> 1:], 1) +else: +mid = rbigint(n._digits[shift:], 1) +hi = rbigint([NULLDIGIT] * ((shift * 3) - size_n), 1) +lo._normalize() +mid._normalize() +hi._normalize() +return hi, mid, lo + +# Declear a simple 2 as constants for our toom cook +POINT2 = rbigint.fromint(2) +def _tc_mul(a, b): +""" +Toom Cook +""" +asize = a.numdigits() +bsize = b.numdigits() + +# Split a & b into hi, mid and lo pieces. +shift = bsize >> 1 +ah, am, al = _tcmul_split(a, shift) +assert ah.sign == 1# the split isn't degenerate + +if a is b: +bh = ah +bm = am +bl = al +else: +bh, bm, bl = _tcmul_split(b, shift) + +# 1. Allocate result space. +ret = rbigint([NULLDIGIT] * (asize + bsize), 1) + +# 2. w points +pO = al.add(ah) +p1 = pO.add(am) +pn1 = pO.sub(am) +pn2 = pn1.add(ah).mul(POINT2).sub(al) + +qO = bl.add(bh) +q1 = qO.add(bm) +qn1 = qO.sub(bm) +qn2 = qn1.add(bh).mul(POINT2).sub(bl) + +w0 = al.mul(bl) +winf = ah.mul(bh) +w1 = p1.mul(q1) +wn1 = pn1.mul(qn1) +wn2 = pn2.mul(qn2) + +# 3. The important stuff +# XXX: Need a faster / 3 and /2 like in GMP! +r0 = w0 +r4 = winf +r3 = _divrem1(wn2.sub(wn1), 3)[0] +r1 = _divrem1(w1.sub(wn1), 2)[0] +r2 = wn1.sub(w0) +r3 = _divrem1(r2.sub(r3), 2)[0].add(r4.mul(POINT2)) +r2 = r2.add(r1).sub(r4) +r1 = r1.sub(r3) + +# Now we fit r+ r2 + r4 into the new string. +# Now we got to add the r1 and r3 in the mid shift. This is TODO (aga, not fixed yet) +pointer = r0.numdigits() +ret._digits[:pointer] = r0
[pypy-commit] pypy improve-rbigint: More fixes to toom cock
Author: stian Branch: improve-rbigint Changeset: r56321:423421c5c9ba Date: 2012-06-23 06:41 +0200 http://bitbucket.org/pypy/pypy/changeset/423421c5c9ba/ Log:More fixes to toom cock diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -36,8 +36,8 @@ KARATSUBA_CUTOFF = 38 KARATSUBA_SQUARE_CUTOFF = 2 * KARATSUBA_CUTOFF -USE_TOOMCOCK = False -TOOMCOOK_CUTOFF = 102 +USE_TOOMCOCK = False # WIP +TOOMCOOK_CUTOFF = 3 # Smallest possible cutoff is 3. Ideal is probably around 150+ # For exponentiation, use the binary left-to-right algorithm # unless the exponent contains more than FIVEARY_CUTOFF digits. @@ -956,30 +956,18 @@ """ A helper for Karatsuba multiplication (k_mul). Takes a bigint "n" and an integer "size" representing the place to -split, and sets low and high such that abs(n) == (high << size) + low, +split, and sets low and high such that abs(n) == (high << (size * 2) + (mid << size) + low, viewing the shift as being by digits. The sign bit is ignored, and the return values are >= 0. """ - -assert size > 0 - -size_n = n.numdigits() -shift = min(size_n, size) - -lo = rbigint(n._digits[:shift], 1) -if size_n >= (shift * 2): -mid = rbigint(n._digits[shift:shift >> 1], 1) -hi = rbigint(n._digits[shift >> 1:], 1) -else: -mid = rbigint(n._digits[shift:], 1) -hi = rbigint([NULLDIGIT] * ((shift * 3) - size_n), 1) +lo = rbigint(n._digits[:size], 1) +mid = rbigint(n._digits[size:size * 2], 1) +hi = rbigint(n._digits[size *2:], 1) lo._normalize() mid._normalize() hi._normalize() return hi, mid, lo -# Declear a simple 2 as constants for our toom cook -POINT2 = rbigint.fromint(2) def _tc_mul(a, b): """ Toom Cook @@ -988,7 +976,7 @@ bsize = b.numdigits() # Split a & b into hi, mid and lo pieces. -shift = bsize >> 1 +shift = asize // 3 ah, am, al = _tcmul_split(a, shift) assert ah.sign == 1# the split isn't degenerate @@ -1006,15 +994,16 @@ pO = al.add(ah) p1 = pO.add(am) pn1 = pO.sub(am) -pn2 = pn1.add(ah).mul(POINT2).sub(al) +pn2 = pn1.add(ah).lshift(1).sub(al) qO = bl.add(bh) q1 = qO.add(bm) qn1 = qO.sub(bm) -qn2 = qn1.add(bh).mul(POINT2).sub(bl) +qn2 = qn1.add(bh).lshift(1).sub(bl) w0 = al.mul(bl) winf = ah.mul(bh) + w1 = p1.mul(q1) wn1 = pn1.mul(qn1) wn2 = pn2.mul(qn2) @@ -1024,26 +1013,29 @@ r0 = w0 r4 = winf r3 = _divrem1(wn2.sub(wn1), 3)[0] -r1 = _divrem1(w1.sub(wn1), 2)[0] +r1 = w1.sub(wn1).rshift(1) r2 = wn1.sub(w0) -r3 = _divrem1(r2.sub(r3), 2)[0].add(r4.mul(POINT2)) +r3 = _divrem1(r2.sub(r3), 2)[0].add(r4.lshift(1)) r2 = r2.add(r1).sub(r4) r1 = r1.sub(r3) # Now we fit r+ r2 + r4 into the new string. # Now we got to add the r1 and r3 in the mid shift. This is TODO (aga, not fixed yet) -pointer = r0.numdigits() -ret._digits[:pointer] = r0._digits +ret._digits[:shift] = r0._digits -pointer2 = pointer + r2.numdigits() -ret._digits[pointer:pointer2] = r2._digits +ret._digits[shift:shift*2] = r2._digits -pointer3 = pointer2 + r4.numdigits() -ret._digits[pointer2:pointer3] = r4._digits +ret._digits[shift*2:(shift*2)+r4.numdigits()] = r4._digits # TODO -#_v_iadd(ret, shift, i, r1, r1.numdigits()) -#_v_iadd(ret, shift >> 1, i, r3, r3.numdigits()) +""" +x and y are rbigints, m >= n required. x.digits[0:n] is modified in place, +by adding y.digits[0:m] to it. Carries are propagated as far as +x[m-1], and the remaining carry (0 or 1) is returned. +Python adaptation: x is addressed relative to xofs! +""" +_v_iadd(ret, shift, shift + r1.numdigits(), r1, r1.numdigits()) +_v_iadd(ret, shift * 2, shift + r3.numdigits(), r3, r3.numdigits()) ret._normalize() return ret ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: On 64bit x can already fit 2*shift ints
Author: stian Branch: improve-rbigint Changeset: r56322:4e53823b9304 Date: 2012-06-23 18:04 +0200 http://bitbucket.org/pypy/pypy/changeset/4e53823b9304/ Log:On 64bit x can already fit 2*shift ints diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -54,9 +54,9 @@ def _widen_digit(x): if not we_are_translated(): assert is_valid_int(x), "widen_digit() takes an int, got a %r" % type(x) -if SHIFT <= 15: -return int(x) -return r_longlong(x) +if LONG_BIT < 64: +return r_longlong(x) +return x def _store_digit(x): if not we_are_translated(): ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Add regular pypy benchmark. The improvement is about 50 times
Author: stian Branch: improve-rbigint Changeset: r56324:a902735aeb26 Date: 2012-06-24 07:55 +0200 http://bitbucket.org/pypy/pypy/changeset/a902735aeb26/ Log:Add regular pypy benchmark. The improvement is about 50 times diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -10,6 +10,7 @@ """ A cutout with some benchmarks. Pypy default: +484.5688 8.637287 12.211942 18.270045 ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Add speedup for all (power of two)**num.
Author: stian Branch: improve-rbigint Changeset: r56325:2e062df94210 Date: 2012-06-24 21:49 +0200 http://bitbucket.org/pypy/pypy/changeset/2e062df94210/ Log:Add speedup for all (power of two)**num. One of the tests ((2**31)**(2**31)) is now 100 times faster (this beats CPython, and even C) diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -8,7 +8,7 @@ from pypy.rpython.lltypesystem import lltype, rffi from pypy.rpython import extregistry -import math, sys +import math, sys, array # note about digit sizes: # In division, the native integer type must be able to hold @@ -459,7 +459,9 @@ "cannot be negative when 3rd argument specified") # XXX failed to implement raise ValueError("bigint pow() too negative") - + +size_b = b.numdigits() + if c is not None: if c.sign == 0: raise ValueError("pow() 3rd argument cannot be 0") @@ -483,9 +485,8 @@ a, temp = a.divmod(c) a = temp -size_b = b.numdigits() - -if not c and size_b == 1 and a.sign == 1: + +elif size_b == 1 and a.sign == 1: digit = b.digit(0) if digit == 0: return rbigint([ONEDIGIT], 1) @@ -495,8 +496,8 @@ adigit = a.digit(0) if adigit == 1: return rbigint([ONEDIGIT], 1) -elif adigit == 2: -return a.lshift(digit-1) +elif adigit & (adigit - 1) == 0: +return a.lshift(((digit-1)*(ptwotable[adigit]-1)) + digit-1) # At this point a, b, and c are guaranteed non-negative UNLESS # c is NULL, in which case a may be negative. */ @@ -518,6 +519,7 @@ z = _help_mult(z, a, c) j >>= 1 size_b -= 1 + else: # Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) # This is only useful in the case where c != None. diff --git a/pypy/rlib/test/test_rbigint.py b/pypy/rlib/test/test_rbigint.py --- a/pypy/rlib/test/test_rbigint.py +++ b/pypy/rlib/test/test_rbigint.py @@ -1,6 +1,6 @@ from __future__ import division import py -import operator, sys +import operator, sys, array from random import random, randint, sample from pypy.rlib.rbigint import rbigint, SHIFT, MASK, KARATSUBA_CUTOFF from pypy.rlib.rbigint import _store_digit diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -20,25 +20,34 @@ 6.647562 Pypy with improvements: -9.474363 -5.797121 -10.068798 -14.770187 -1.620009 -12.054951 -14.292367 -6.440351 +9.451896 +1.122038 +5.787821 +9.937016 +14.927304 +0.016683 +12.018289 +14.261727 +6.434917 """ -t = time() +"""t = time() num = rbigint.fromint(1000) for n in xrange(1): rbigint.pow(rbigint.fromint(2), num) +print time() - t""" + +t = time() +num = rbigint.fromint(1) +for n in xrange(31): +rbigint.pow(rbigint.pow(rbigint.fromint(2), rbigint.fromint(n)), num) + + print time() - t - + t = time() num = rbigint.pow(rbigint.fromint(1), rbigint.fromint(2 ** 8)) for n in xrange(6): ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Speedup floordiv by the power of two
Author: stian Branch: improve-rbigint Changeset: r56327:0d3da129 Date: 2012-06-24 22:30 +0200 http://bitbucket.org/pypy/pypy/changeset/0d3da129/ Log:Speedup floordiv by the power of two diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -412,6 +412,15 @@ return div def floordiv(self, other): +if other.numdigits() == 1 and other.sign == 1: +digit = other.digit(0) + +if digit == 1: +return self +elif digit & (digit - 1) == 0: +div = self.rshift(ptwotable[digit]) +return div + div, mod = self.divmod(other) return div diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -10,6 +10,7 @@ """ A cutout with some benchmarks. Pypy default: +5.147583 484.5688 334.611903 8.637287 @@ -21,6 +22,7 @@ 6.647562 Pypy with improvements: +2.307890 9.451896 1.122038 5.787821 @@ -32,6 +34,14 @@ 6.434917 """ + +t = time() +num = rbigint.fromint(1) +for n in xrange(8000): +rbigint.floordiv(num, rbigint.fromint(2)) + + +print time() - t t = time() num = rbigint.fromint(1000) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Reduce operations on mod and floordiv (without power of two) = more speed
Author: stian Branch: improve-rbigint Changeset: r56328:1d2cb7e2302d Date: 2012-06-24 23:38 +0200 http://bitbucket.org/pypy/pypy/changeset/1d2cb7e2302d/ Log:Reduce operations on mod and floordiv (without power of two) = more speed diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -161,8 +161,8 @@ # This function is marked as pure, so you must not call it and # then modify the result. if b: -return rbigint([ONEDIGIT], 1) -return rbigint() +return ONERBIGINT +return NULLRBIGINT @staticmethod def fromlong(l): @@ -421,14 +421,18 @@ div = self.rshift(ptwotable[digit]) return div -div, mod = self.divmod(other) +div, mod = _divrem(self, other) +if mod.sign * other.sign == -1: +div = div.sub(ONERBIGINT) return div def div(self, other): return self.floordiv(other) def mod(self, other): -div, mod = self.divmod(other) +div, mod = _divrem(self, other) +if mod.sign * other.sign == -1: +mod = mod.add(other) return mod def divmod(v, w): @@ -451,7 +455,7 @@ div, mod = _divrem(v, w) if mod.sign * w.sign == -1: mod = mod.add(w) -div = div.sub(rbigint([_store_digit(1)], 1)) +div = div.sub(ONERBIGINT) return div, mod def pow(a, b, c=None): @@ -498,13 +502,13 @@ elif size_b == 1 and a.sign == 1: digit = b.digit(0) if digit == 0: -return rbigint([ONEDIGIT], 1) +return ONERBIGINT elif digit == 1: return a elif a.numdigits() == 1: adigit = a.digit(0) if adigit == 1: -return rbigint([ONEDIGIT], 1) +return ONERBIGINT elif adigit & (adigit - 1) == 0: return a.lshift(((digit-1)*(ptwotable[adigit]-1)) + digit-1) @@ -745,6 +749,9 @@ return "" % (self._digits, self.sign, self.str()) +ONERBIGINT = rbigint([ONEDIGIT], 1) +NULLRBIGINT = rbigint() + #_ # Helper Functions @@ -866,7 +873,7 @@ while i >= 0 and a.digit(i) == b.digit(i): i -= 1 if i < 0: -return rbigint() +return NULLRBIGINT if a.digit(i) < b.digit(i): sign = -1 a, b = b, a @@ -1464,9 +1471,7 @@ (size_a == size_b and a.digit(size_a-1) < b.digit(size_b-1))): # |a| < |b| -z = rbigint() # result is 0 -rem = a -return z, rem +return NULLRBIGINT, a# result is 0 if size_b == 1: z, urem = _divrem1(a, b.digit(0)) rem = rbigint([_store_digit(urem)], int(urem != 0)) diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -11,6 +11,7 @@ A cutout with some benchmarks. Pypy default: 5.147583 +5.139127 484.5688 334.611903 8.637287 @@ -22,16 +23,17 @@ 6.647562 Pypy with improvements: -2.307890 -9.451896 -1.122038 -5.787821 -9.937016 -14.927304 -0.016683 -12.018289 -14.261727 -6.434917 +2.291724 +4.616600 +9.538857 +1.102726 +4.820049 +9.899771 +14.733251 +0.016657 +11.992919 +14.144412 +6.404446 """ @@ -44,6 +46,14 @@ print time() - t t = time() +num = rbigint.fromint(1) +for n in xrange(8000): +rbigint.floordiv(num, rbigint.fromint(3)) + + +print time() - t + +t = time() num = rbigint.fromint(1000) for n in xrange(1): rbigint.pow(rbigint.fromint(2), num) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Remove a unintensional import
Author: stian Branch: improve-rbigint Changeset: r56329:4acc694be4f5 Date: 2012-06-25 00:36 +0200 http://bitbucket.org/pypy/pypy/changeset/4acc694be4f5/ Log:Remove a unintensional import diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -8,7 +8,7 @@ from pypy.rpython.lltypesystem import lltype, rffi from pypy.rpython import extregistry -import math, sys, array +import math, sys # note about digit sizes: # In division, the native integer type must be able to hold ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Fix a bug with floordiv caused by my power of two code that allowed div by 0
Author: stian Branch: improve-rbigint Changeset: r56330:ea6df5628183 Date: 2012-06-25 02:30 +0200 http://bitbucket.org/pypy/pypy/changeset/ea6df5628183/ Log:Fix a bug with floordiv caused by my power of two code that allowed div by 0 diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -414,10 +414,9 @@ def floordiv(self, other): if other.numdigits() == 1 and other.sign == 1: digit = other.digit(0) - if digit == 1: return self -elif digit & (digit - 1) == 0: +elif digit and digit & (digit - 1) == 0: div = self.rshift(ptwotable[digit]) return div ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Introduce int128 and int cache.
Author: stian Branch: improve-rbigint Changeset: r56331:14ff425f3744 Date: 2012-06-25 06:58 +0200 http://bitbucket.org/pypy/pypy/changeset/14ff425f3744/ Log:Introduce int128 and int cache. Also find a new karatsuba cutoff that is fine with the new settings. Some things are slower (especially creating new ints). But generally, it's a major speedup. 4 failing tests, mostly due to not being able to cast down to int. Hash is also wrong (critical). Not JIT support yet I suppose. diff --git a/pypy/jit/codewriter/jtransform.py b/pypy/jit/codewriter/jtransform.py --- a/pypy/jit/codewriter/jtransform.py +++ b/pypy/jit/codewriter/jtransform.py @@ -462,6 +462,11 @@ rewrite_op_llong_floordiv_zer = _do_builtin_call rewrite_op_llong_mod = _do_builtin_call rewrite_op_llong_mod_zer = _do_builtin_call +rewrite_op_lllong_abs = _do_builtin_call +rewrite_op_lllong_floordiv = _do_builtin_call +rewrite_op_lllong_floordiv_zer = _do_builtin_call +rewrite_op_lllong_mod = _do_builtin_call +rewrite_op_lllong_mod_zer = _do_builtin_call rewrite_op_ullong_floordiv = _do_builtin_call rewrite_op_ullong_floordiv_zer = _do_builtin_call rewrite_op_ullong_mod = _do_builtin_call diff --git a/pypy/jit/codewriter/support.py b/pypy/jit/codewriter/support.py --- a/pypy/jit/codewriter/support.py +++ b/pypy/jit/codewriter/support.py @@ -250,6 +250,101 @@ _ll_1_ll_math_ll_math_sqrt = ll_math.ll_math_sqrt +# long long long support +# - + +def u_to_longlonglong(x): +return rffi.cast(lltype.SignedLongLongLong, x) + +def _ll_1_lllong_invert(xll): +y = ~r_ulonglonglong(xll) +return u_to_longlonglong(y) + +def _ll_2_lllong_lt(xll, yll): +return xll < yll + +def _ll_2_lllong_le(xll, yll): +return xll <= yll + +def _ll_2_lllong_eq(xll, yll): +return xll == yll + +def _ll_2_lllong_ne(xll, yll): +return xll != yll + +def _ll_2_lllong_gt(xll, yll): +return xll > yll + +def _ll_2_lllong_ge(xll, yll): +return xll >= yll + +def _ll_2_lllong_add(xull, yull): +z = (xull) + (yull) +return (z) + +def _ll_2_lllong_sub(xull, yull): +z = (xull) - (yull) +return (z) + +def _ll_2_lllong_mul(xull, yull): +z = (xull) * (yull) +return (z) + +def _ll_2_lllong_and(xull, yull): +z = (xull) & (yull) +return (z) + +def _ll_2_lllong_or(xull, yull): +z = (xull) | (yull) +return (z) + +def _ll_2_lllong_xor(xull, yull): +z = (xull) ^ (yull) +return (z) + +def _ll_2_lllong_lshift(xlll, y): +return xll << y + +def _ll_2_lllong_rshift(xlll, y): +return xll >> y + +def _ll_1_lllong_from_int(x): +return r_longlonglong(intmask(x)) + +def _ll_1_lllong_from_uint(x): +return r_longlonglong(r_uint(x)) + +def _ll_1_lllong_to_int(xlll): +return intmask(xll) + +def _ll_1_lllong_from_float(xf): +return r_longlonglong(xf) + +def _ll_1_llong_to_float(xll): +return float(rffi.cast(lltype.SignedLongLongLong, xlll)) + +def _ll_1_llong_abs(xll): +if xll < 0: +return -xll +else: +return xll + +def _ll_2_llong_floordiv(xll, yll): +return llop.lllong_floordiv(lltype.SignedLongLongLong, xll, yll) + +def _ll_2_llong_floordiv_zer(xll, yll): +if yll == 0: +raise ZeroDivisionError +return llop.lllong_floordiv(lltype.SignedLongLongLong, xll, yll) + +def _ll_2_llong_mod(xll, yll): +return llop.lllong_mod(lltype.SignedLongLongLong, xll, yll) + +def _ll_2_llong_mod_zer(xll, yll): +if yll == 0: +raise ZeroDivisionError +return llop.lllong_mod(lltype.SignedLongLongLong, xll, yll) + # long long support # - diff --git a/pypy/rlib/rarithmetic.py b/pypy/rlib/rarithmetic.py --- a/pypy/rlib/rarithmetic.py +++ b/pypy/rlib/rarithmetic.py @@ -87,6 +87,10 @@ LONG_BIT_SHIFT += 1 assert LONG_BIT_SHIFT < 99, "LONG_BIT_SHIFT value not found?" +LONGLONGLONG_BIT = 128 +LONGLONGLONG_MASK = (2**LONGLONGLONG_BIT)-1 +LONGLONGLONG_TEST = 2**(LONGLONGLONG_BIT-1) + """ int is no longer necessarily the same size as the target int. We therefore can no longer use the int type as it is, but need @@ -122,6 +126,17 @@ n -= 2*LONGLONG_TEST return r_longlong(n) +def longlonglongmask(n): +""" +NOT_RPYTHON +""" +assert isinstance(n, (int, long)) +n = long(n) +n &= LONGLONGLONG_MASK +if n >= LONGLONGLONG_TEST: +n -= 2*LONGLONGLONG_TEST +return r_longlonglong(n) + def widen(n): from pypy.rpython.lltypesystem import lltype if _should_widen_type(lltype.typeOf(n)): @@ -475,6 +490,7 @@ r_longlong = build_int('r_longlong', True, 64) r_ulonglong = build_int('r_ulonglong', False, 64) +r_longlonglong = build_int('r_longlonglong', True, 128) longlongmax = r_longlong(LONGLONG_TEST
[pypy-commit] pypy improve-rbigint: We need the cast, otherwise I'm sure it won't work on 32bit. On 64bit it links to the same type anyway
Author: stian Branch: improve-rbigint Changeset: r56333:4fee44dbf222 Date: 2012-06-25 08:38 +0200 http://bitbucket.org/pypy/pypy/changeset/4fee44dbf222/ Log:We need the cast, otherwise I'm sure it won't work on 32bit. On 64bit it links to the same type anyway diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -68,8 +68,7 @@ elif SHIFT <= 31: return rffi.cast(rffi.INT, x) elif SHIFT <= 63: -return int(x) -#return rffi.cast(rffi.LONGLONG, x) +return rffi.cast(rffi.LONGLONG, x) else: raise ValueError("SHIFT too large!") @@ -78,8 +77,8 @@ #return rffi.cast(lltype.Signed, x) def _load_unsigned_digit(x): -#return r_ulonglong(x) -return rffi.cast(lltype.Unsigned, x) +return r_ulonglong(x) +#return rffi.cast(lltype.Unsigned, x) NULLDIGIT = _store_digit(0) ONEDIGIT = _store_digit(1) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Necessary fixes for 32bit, and the last cache int number
Author: stian Branch: improve-rbigint Changeset: r56334:a06e8a99fbc0 Date: 2012-06-25 17:22 +0200 http://bitbucket.org/pypy/pypy/changeset/a06e8a99fbc0/ Log:Necessary fixes for 32bit, and the last cache int number diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -17,7 +17,7 @@ #SHIFT = (LONG_BIT // 2) - 1 SHIFT = 63 -MASK = int((1 << SHIFT) - 1) +MASK = long((1 << SHIFT) - 1) FLOAT_MULTIPLIER = float(1 << LONG_BIT) # Because it works. CACHE_INTS = 1024 # CPython do 256 @@ -137,9 +137,7 @@ # then modify the result. check_regular_int(intval) -cache = False - -if intval != 0 and intval < CACHE_INTS and intval > -CACHE_INTS: +if intval != 0 and intval <= CACHE_INTS and intval >= -CACHE_INTS: return INTCACHE[intval] if intval < 0: @@ -158,9 +156,10 @@ if SHIFT >= 63: carry = ival >> SHIFT if carry: -return rbigint([intmask((ival)), intmask(carry)], sign) +return rbigint([_store_digit(_mask_digit(ival)), +_store_digit(_mask_digit(carry))], sign) else: -return rbigint([intmask(ival)], sign) +return rbigint([_store_digit(_mask_digit(ival))], sign) t = ival ndigits = 0 @@ -581,8 +580,8 @@ # j = (m+) % SHIFT = (m+) - (i * SHIFT) # (computed without doing "i * SHIFT", which might overflow) j = size_b % 5 -"""if j != 0: -j = 5 - j""" +if j != 0: +j = 5 - j if not we_are_translated(): assert j == (size_b*SHIFT+4)//5*5 - size_b*SHIFT # @@ -783,7 +782,7 @@ self.sign, self.str()) INTCACHE = {} -for x in range(1, CACHE_INTS): +for x in range(1, CACHE_INTS+1): numList = [_store_digit(x)] INTCACHE[x] = rbigint(numList, 1) INTCACHE[-x] = rbigint(numList, -1) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Ensure correct type when doing rshift
Author: stian Branch: improve-rbigint Changeset: r56337:453a2fb08ae3 Date: 2012-06-26 06:28 +0200 http://bitbucket.org/pypy/pypy/changeset/453a2fb08ae3/ Log:Ensure correct type when doing rshift diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -31,10 +31,12 @@ SHIFT = 63 MASK = long((1 << SHIFT) - 1) UDIGIT_TYPE = r_ulonglong +UDIGIT_MASK = longlongmask else: SHIFT = 31 MASK = int((1 << SHIFT) - 1) UDIGIT_TYPE = r_uint +UDIGIT_MASK = intmask FLOAT_MULTIPLIER = float(1 << LONG_BIT) # Because it works. @@ -486,8 +488,7 @@ if digit == 1: return self elif digit and digit & (digit - 1) == 0: -div = self.rshift(ptwotable[digit]) -return div +return self.rshift(ptwotable[digit]) div, mod = _divrem(self, other) if mod.sign * other.sign == -1: @@ -727,11 +728,11 @@ wordshift = int_other // SHIFT newsize = self.numdigits() - wordshift if newsize <= 0: -return rbigint() +return NULLRBIGINT loshift = int_other % SHIFT hishift = SHIFT - loshift -lomask = intmask((r_uint(1) << hishift) - 1) +lomask = UDIGIT_MASK((UDIGIT_TYPE(1) << hishift) - 1) himask = MASK ^ lomask z = rbigint([NULLDIGIT] * newsize, self.sign) i = 0 ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Some more tweaks + rshift and lshift benchmark
Author: stian Branch: improve-rbigint Changeset: r56338:713dc82e5b4a Date: 2012-06-26 06:52 +0200 http://bitbucket.org/pypy/pypy/changeset/713dc82e5b4a/ Log:Some more tweaks + rshift and lshift benchmark diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -420,7 +420,7 @@ if other.sign == 0: return self if self.sign == 0: -return rbigint(other._digits[:], -other.sign) +return rbigint(other._digits, -other.sign) if self.sign == other.sign: result = _x_sub(self, other) else: @@ -447,7 +447,7 @@ if digit == 0: return rbigint() elif digit == 1: -return rbigint(b._digits[:], a.sign * b.sign) +return rbigint(b._digits, a.sign * b.sign) elif bsize == 1: result = rbigint([NULLDIGIT] * 2, a.sign * b.sign) carry = b.widedigit(0) * digit @@ -737,10 +737,11 @@ z = rbigint([NULLDIGIT] * newsize, self.sign) i = 0 j = wordshift +newdigit = UDIGIT_TYPE(0) while i < newsize: newdigit = (self.digit(j) >> loshift) & lomask if i+1 < newsize: -newdigit |= intmask(self.digit(j+1) << hishift) & himask +newdigit |= UDIGIT_MASK(self.digit(j+1) << hishift) & himask z.setdigit(i, newdigit) i += 1 j += 1 diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -23,6 +23,8 @@ 6.647562 Pypy with improvements: +2.522946 +4.600970 2.126048 4.276203 9.662745 @@ -39,6 +41,22 @@ """ t = time() +num = rbigint.fromint(10) +for n in xrange(16000): +rbigint.rshift(num, 16) + + +print time() - t + +t = time() +num = rbigint.fromint(10) +for n in xrange(16000): +rbigint.lshift(num, 4) + + +print time() - t + +t = time() num = rbigint.fromint(1) for n in xrange(8000): rbigint.floordiv(num, rbigint.fromint(2)) ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: A little sad news, lshift with tiny numbers are nearly twice as slow using int128.
Author: stian Branch: improve-rbigint Changeset: r56339:5f2143a12b5c Date: 2012-06-26 07:21 +0200 http://bitbucket.org/pypy/pypy/changeset/5f2143a12b5c/ Log:A little sad news, lshift with tiny numbers are nearly twice as slow using int128. It's not a slow operation tho, 2.875e-08 per round. For comparesment 2**n (![0->1]) takes 9.66e-04 per round (and thats 50 times faster than unmodified pypy). Even a regular add operation takes 1e-05 per round. diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -690,10 +690,9 @@ accum >>= SHIFT i += 1 j += 1 -if remshift: -z.setdigit(newsize - 1, accum) -else: -assert not accum + +z.setdigit(newsize - 1, accum) + z._normalize() return z diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -8,8 +8,12 @@ def entry_point(argv): """ +All benchmarks are run using --opt=2 and minimark gc (default). + A cutout with some benchmarks. Pypy default: +2.316023 +2.418211 5.147583 5.139127 484.5688 ___ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
[pypy-commit] pypy improve-rbigint: Add some stuff regarding div. Not really working yet
Author: stian Branch: improve-rbigint Changeset: r56341:e401dc346887 Date: 2012-06-27 17:38 +0200 http://bitbucket.org/pypy/pypy/changeset/e401dc346887/ Log:Add some stuff regarding div. Not really working yet diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -29,15 +29,16 @@ #SHIFT = (LONG_BIT // 2) - 1 if SUPPORT_INT128: SHIFT = 63 -MASK = long((1 << SHIFT) - 1) +BASE = long(1 << SHIFT) UDIGIT_TYPE = r_ulonglong UDIGIT_MASK = longlongmask else: SHIFT = 31 -MASK = int((1 << SHIFT) - 1) +BASE = int(1 << SHIFT) UDIGIT_TYPE = r_uint UDIGIT_MASK = intmask - + +MASK = BASE - 1 FLOAT_MULTIPLIER = float(1 << LONG_BIT) # Because it works. CACHE_INTS = 1024 # CPython do 256 @@ -65,6 +66,9 @@ USE_TOOMCOCK = False # WIP TOOMCOOK_CUTOFF = 3 # Smallest possible cutoff is 3. Ideal is probably around 150+ +# Use N**2 division when number of digits are smaller than this. +DIV_LIMIT = KARATSUBA_CUTOFF + # For exponentiation, use the binary left-to-right algorithm # unless the exponent contains more than FIVEARY_CUTOFF digits. # In that case, do 5 bits at a time. The potential drawback is that @@ -1482,21 +1486,66 @@ z._normalize() return z +def _v_lshift(z, a, m, d): +""" Shift digit vector a[0:m] d bits left, with 0 <= d < SHIFT. Put +* result in z[0:m], and return the d bits shifted out of the top. +""" + +carry = 0 +assert 0 <= d and d < SHIFT +for i in range(m): +acc = a.widedigit(i) << d | carry +z.setdigit(i, acc) +carry = acc >> SHIFT + +return carry + +def _v_rshift(z, a, m, d): +""" Shift digit vector a[0:m] d bits right, with 0 <= d < PyLong_SHIFT. Put +* result in z[0:m], and return the d bits shifted out of the bottom. +""" + +carry = 0 +acc = _widen_digit(0) +mask = (1 << d) - 1 + +assert 0 <= d and d < SHIFT +for i in range(m-1, 0, -1): +acc = carry << SHIFT | a.digit(i) +carry = acc & mask +z.setdigit(i, acc >> d) + +return carry + def _x_divrem(v1, w1): """ Unsigned bigint division with remainder -- the algorithm """ + size_w = w1.numdigits() d = (UDIGIT_TYPE(MASK)+1) // (w1.udigit(size_w-1) + 1) assert d <= MASK# because the first digit of w1 is not zero d = longlongmask(d) v = _muladd1(v1, d) w = _muladd1(w1, d) -size_v = v.numdigits() -size_w = w.numdigits() -assert size_v >= size_w and size_w >= 1 # (stian: Adding d doesn't necessary mean it will increase by 1), Assert checks by div() +size_v = v1.numdigits() +size_w = w1.numdigits() +assert size_v >= size_w and size_w >= 1 # (Assert checks by div() +"""v = rbigint([NULLDIGIT] * (size_v + 1)) +w = rbigint([NULLDIGIT] * (size_w)) + +d = SHIFT - bits_in_digit(w1.digit(size_w-1)) +carry = _v_lshift(w, w1, size_w, d) +assert carry == 0 +carrt = _v_lshift(v, v1, size_v, d) +if carry != 0 or v.digit(size_v - 1) >= w.digit(size_w-1): +v.setdigit(size_v, carry) +size_v += 1""" + size_a = size_v - size_w + 1 a = rbigint([NULLDIGIT] * size_a, 1) +wm1 = w.widedigit(size_w-1) +wm2 = w.widedigit(size_w-2) j = size_v k = size_a - 1 while k >= 0: @@ -1504,20 +1553,24 @@ vj = 0 else: vj = v.widedigit(j) + carry = 0 - -if vj == w.widedigit(size_w-1): +vj1 = v.widedigit(j-1) + +if vj == wm1: q = MASK else: -q = ((vj << SHIFT) + v.widedigit(j-1)) // w.widedigit(size_w-1) +q = ((vj << SHIFT) + vj1) // wm1 -while (w.widedigit(size_w-2) * q > + +vj2 = v.widedigit(j-2) +while (wm2 * q > (( (vj << SHIFT) -+ v.widedigit(j-1) -- q * w.widedigit(size_w-1) ++ vj1 +- q * wm1 ) << SHIFT) -+ v.widedigit(j-2)): ++ vj2): q -= 1 i = 0 while i < size_w and i+k < size_v: @@ -1556,6 +1609,95 @@ rem, _ = _divrem1(v, d) return a, rem +""" +Didn't work as expected. Someone want to look over this? +size_v = v1.numdigits() +size_w = w1.numdigits() + +assert size_v >= size_w and size_w >= 2 + +v = rbigint([NULLDIGIT] * (size_v + 1)) +w = rbigint([NULLDIGIT] * size_w) + +# Normalization +d = SHIFT - bits_in_digit(w1.digit(siz
[pypy-commit] pypy improve-rbigint: Add some _always_inline_ (for some reason it doesn't always happend). This makes lshift 15% faster
Author: stian Branch: improve-rbigint Changeset: r56344:f89eae2a4218 Date: 2012-07-04 01:34 +0200 http://bitbucket.org/pypy/pypy/changeset/f89eae2a4218/ Log:Add some _always_inline_ (for some reason it doesn't always happend). This makes lshift 15% faster diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py --- a/pypy/rlib/rbigint.py +++ b/pypy/rlib/rbigint.py @@ -89,7 +89,7 @@ return r_longlonglong(x) else: return r_longlong(x) - +_widen_digit._always_inline_ = True def _store_digit(x): """if not we_are_translated(): assert is_valid_int(x), "store_digit() takes an int, got a %r" % type(x)""" @@ -102,6 +102,7 @@ else: raise ValueError("SHIFT too large!") _store_digit._annspecialcase_ = 'specialize:argtype(0)' +_store_digit._always_inline_ = True def _load_digit(x): if SHIFT < LONG_BIT: # This would be the case for any SHIFT < LONG_BIT @@ -109,6 +110,7 @@ else: # x already is a type large enough, just not as fast. return x +_load_digit._always_inline_ = True def _load_unsigned_digit(x): if SHIFT < LONG_BIT: # This would be the case for any SHIFT < LONG_BIT @@ -117,6 +119,7 @@ # This needs a performance test on 32bit return rffi.cast(rffi.ULONGLONG, x) #return r_ulonglong(x) +_load_unsigned_digit._always_inline_ = True NULLDIGIT = _store_digit(0) ONEDIGIT = _store_digit(1) @@ -151,25 +154,30 @@ def digit(self, x): """Return the x'th digit, as an int.""" return _load_digit(self._digits[x]) - +digit._always_inline_ = True + def widedigit(self, x): """Return the x'th digit, as a long long int if needed to have enough room to contain two digits.""" return _widen_digit(_load_digit(self._digits[x])) - +widedigit._always_inline_ = True + def udigit(self, x): """Return the x'th digit, as an unsigned int.""" return _load_unsigned_digit(self._digits[x]) - +udigit._always_inline_ = True + def setdigit(self, x, val): val = _mask_digit(val) assert val >= 0 self._digits[x] = _store_digit(val) setdigit._annspecialcase_ = 'specialize:argtype(2)' +setdigit._always_inline_ = True def numdigits(self): return len(self._digits) - +numdigits._always_inline_ = True + @staticmethod @jit.elidable def fromint(intval): @@ -708,7 +716,8 @@ z._normalize() return z - +lshift._always_inline_ = True # It's so fast that it's always benefitial. + @jit.elidable def lqshift(self, int_other): " A quicker one with much less checks, int_other is valid and for the most part constant." @@ -727,6 +736,7 @@ z.setdigit(oldsize, accum) z._normalize() return z +lqshift._always_inline_ = True # It's so fast that it's always benefitial. @jit.elidable def rshift(self, int_other, dont_invert=False): @@ -761,7 +771,8 @@ j += 1 z._normalize() return z - +rshift._always_inline_ = True # It's so fast that it's always benefitial. + @jit.elidable def and_(self, other): return _bitwise(self, '&', other) @@ -1690,15 +1701,15 @@ def _divrem(a, b): """ Long division with remainder, top-level routine """ -size_a = _load_unsigned_digit(a.numdigits()) -size_b = _load_unsigned_digit(b.numdigits()) +size_a = a.numdigits() +size_b = b.numdigits() if b.sign == 0: raise ZeroDivisionError("long division or modulo by zero") if (size_a < size_b or (size_a == size_b and - a.digit(size_a-1) < b.digit(size_b-1))): + a.digit(abs(size_a-1)) < b.digit(abs(size_b-1: # |a| < |b| return NULLRBIGINT, a# result is 0 if size_b == 1: diff --git a/pypy/translator/goal/targetbigintbenchmark.py b/pypy/translator/goal/targetbigintbenchmark.py --- a/pypy/translator/goal/targetbigintbenchmark.py +++ b/pypy/translator/goal/targetbigintbenchmark.py @@ -12,37 +12,38 @@ A cutout with some benchmarks. Pypy default: -2.777119 -2.316023 -2.418211 -5.147583 -5.139127 -484.5688 -334.611903 -8.637287 -12.211942 -18.270045 -2.512140 -14.148920 -18.576713 -6.647562 - +2.803071 +2.366586 +2.428205 +4.408400 +4.424533 +537.338 +268.3339 +8.548186 +12.197392 +17.629869 +2.360716 +14.315827 +