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 == 0:
+ raise ValueError("pow() 3rd argument cannot be 0")
+
+ # if modulus < 0:
+ # negativeOutput = True
+ # modulus = -modulus
+ if c.sign < 0:
+ negativeOutput = True
+ c = c.neg()
+
+ # if modulus == 1:
+ # return 0
+ if c.numdigits() == 1 and c._digits[0] == ONEDIGIT:
+ return NULLRBIGINT
+
+ # Reduce base by modulus in some cases:
+ # 1. If base < 0. Forcing the base non-neg makes things easier.
+ # 2. If base is obviously larger than the modulus. The "small
+ # exponent" case later can multiply directly by base repeatedly,
+ # while the "large exponent" case multiplies directly by base 31
+ # times. It can be unboundedly faster to multiply by
+ # base % modulus instead.
+ # We could _always_ do this reduction, but mod() isn't cheap,
+ # 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:
+ return a
+ elif a.numdigits() == 1:
+ adigit = a.digit(0)
+ if adigit == 1:
+ if a.sign == -1 and b % 2:
+ return ONENEGATIVERBIGINT
+ return ONERBIGINT
+ elif adigit & (adigit - 1) == 0:
+ ret = a.lshift(((b-1)*(ptwotable[adigit]-1)) + b-1)
+ if a.sign == -1 and not b % 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. */
+
+ z = rbigint([ONEDIGIT], 1, 1)
+
+ # python adaptation: moved macros REDUCE(X) and MULT(X, Y, result)
+ # into helper function result = _help_mult(x, y, c)
+ # 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:
+ z = _help_mult(z, a, c)
+ j >>= 1
+
+ if negativeOutput and z.sign != 0:
+ z = z.sub(c)
+ return z
+
+ @jit.elidable
def neg(self):
return rbigint(self._digits, -self.sign, self.numdigits())
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,13 @@
r2 = op1 ** op2
assert r1.tolong() == r2
+ 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]:
+ rl_op1 = rbigint.fromlong(op1)
+ r1 = rl_op1.int_pow(op2)
+ r2 = op1 ** op2
+ assert r1.tolong() == r2
def test_touint(self):
result = r_uint(sys.maxint + 42)
rl = rbigint.fromint(sys.maxint).add(rbigint.fromint(42))
@@ -781,6 +788,20 @@
assert div.tolong() == _div
assert rem.tolong() == _rem
+ def test_int_divmod(self):
+ x = 12345678901234567890L
+ for i in range(10):
+ y = randint(0, 1 << 12)
+ for sx, sy in (1, 1), (1, -1), (-1, -1), (-1, 1):
+ sx *= x
+ sy *= y
+ f1 = rbigint.fromlong(sx)
+ div, rem = f1.int_divmod(sy)
+ _div, _rem = divmod(sx, sy)
+ print sx, sy, " | ", div.tolong(), rem.tolong()
+ assert div.tolong() == _div
+ assert rem.tolong() == _rem
+
# testing Karatsuba stuff
def test__v_iadd(self):
f1 = bigint([lobj.MASK] * 10, 1)
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
