Author: stian
Branch: bigint-with-int
Changeset: r65991:9fbd5a1f8450
Date: 2013-08-05 05:50 +0200
http://bitbucket.org/pypy/pypy/changeset/9fbd5a1f8450/
Log: Some fixes, some debug code.
diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py
--- a/rpython/rlib/rbigint.py
+++ b/rpython/rlib/rbigint.py
@@ -42,6 +42,7 @@
LONG_TYPE = rffi.LONGLONG
MASK = int((1 << SHIFT) - 1)
+MIN_VALUE = int((-1 << SHIFT))
FLOAT_MULTIPLIER = float(1 << SHIFT)
# Debugging digit array access.
@@ -615,10 +616,18 @@
def int_add(self, other):
if other == 0:
return self
- if self.sign == 0:
+ elif self.sign == 0:
return rbigint.fromint(other)
+ elif other == MIN_VALUE:
+ # Fallback to long.
+ return self.add(rbigint.fromint(other))
+
+ digit = UDIGIT_TYPE(abs(other))
+
+ assert digit > 0 # Required.
+
if (self.sign > 0 and other > 0) or (self.sign < 0 and other < 0):
- result = _x_int_add(self, abs(other))
+ result = _x_int_add(self, digit)
else:
# XXX: Improve.
result = _x_sub(rbigint.fromint(other), self)
@@ -643,12 +652,17 @@
def int_sub(self, other):
if other == 0:
return self
- if self.sign == 0:
+ elif self.sign == 0:
return rbigint.fromint(-1 * other)
+
+ if other == MIN_VALUE:
+ # Fallback to long.
+ return self.sub(rbigint.fromint(other))
+
if (self.sign > 0 and other > 0) or (self.sign < 0 and other < 0):
- result = _x_int_sub(self, abs(other))
+ result = _x_int_sub(self, other)
else:
- result = _x_int_add(self, abs(other))
+ result = _x_int_add(self, UDIGIT_TYPE(abs(other)))
result.sign *= self.sign
return result
@@ -700,6 +714,11 @@
@jit.elidable
def int_mul(self, b):
""" Mul with int. """
+ if b == MIN_VALUE:
+ # Fallback to long.
+ return self.mul(rbigint.fromint(b))
+
+ digit = _widen_digit(b)
asize = self.numdigits()
if self.sign == 0 or b == 0:
@@ -711,7 +730,7 @@
elif self._digits[0] == ONEDIGIT:
return rbigint.fromint(self.sign * b)
- res = self.widedigit(0) * abs(b)
+ res = self.widedigit(0) * digit
carry = res >> SHIFT
if carry:
return rbigint([_store_digit(res & MASK),
_store_digit(carry)], self.sign * (-1 if b < 0 else 1), 2)
@@ -719,7 +738,7 @@
return rbigint([_store_digit(res & MASK)], self.sign * (-1 if
b < 0 else 1), 1)
else:
- result = _x_int_mul(self, abs(b))
+ result = _x_int_mul(self, digit)
result.sign = self.sign * (-1 if b < 0 else 1)
return result
@@ -741,9 +760,9 @@
digit = other.digit(0)
if digit == 1:
return self
- elif digit and digit & (digit - 1) == 0:
+ """elif digit and digit & (digit - 1) == 0:
return self.rshift(ptwotable[digit])
-
+ """
div, mod = _divrem(self, other)
if mod.sign * other.sign == -1:
if div.sign == 0:
@@ -754,17 +773,21 @@
@jit.elidable
def int_floordiv(self, other):
-
if other == 0:
raise ZeroDivisionError("long division or modulo by zero")
-
+ elif other == MIN_VALUE:
+ # Fallback to long.
+ return self.floordiv(rbigint.fromint(other))
+
digit = abs(other)
+ assert digit > 0
+
if self.sign == 1 and other > 0:
if digit == 1:
return self
- elif digit and digit & (digit - 1) == 0:
+ """elif digit & (digit - 1) == 0:
return self.rshift(ptwotable[digit])
-
+ """
div, mod = _divrem1(self, digit)
if mod != 0 and self.sign * (-1 if other < 0 else 1) == -1:
@@ -823,6 +846,9 @@
def int_mod(self, other):
if self.sign == 0:
return NULLRBIGINT
+ elif other == MIN_VALUE:
+ # Fallback to long.
+ self.mod(rbigint.fromint(other))
digit = abs(other)
@@ -892,13 +918,16 @@
if w == 0:
raise ZeroDivisionError("long division or modulo by zero")
+ digit = abs(w)
wsign = (-1 if w < 0 else 1)
- if v.sign != wsign:
+ if digit >= MASK or not (digit > 0) 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))
- div, mod = _divrem1(v, abs(w))
+ assert digit > 0
+
+ div, mod = _divrem1(v, digit)
mod = rbigint.fromint(mod)
mod.sign = wsign
@@ -1353,14 +1382,11 @@
def _x_int_add(a, b):
""" Add the absolute values of one bigint and one int. """
size_a = a.numdigits()
-
z = rbigint([NULLDIGIT] * (size_a + 1), 1)
- i = UDIGIT_TYPE(0)
-
carry = a.udigit(0) + b
z.setdigit(0, carry)
carry >>= SHIFT
- i += 1
+ i = UDIGIT_TYPE(1)
while i < size_a:
carry += a.udigit(i)
z.setdigit(i, carry)
@@ -1412,6 +1438,9 @@
#borrow &= 1
i += 1
+ if borrow != 0:
+ print a.str(), " minus ", b.str()
+
assert borrow == 0
z._normalize()
return z
@@ -1420,23 +1449,22 @@
""" Subtract the absolute values of one rbigint and one integer. """
size_a = a.numdigits()
+
sign = 1
-
if size_a == 1:
- # Find highest digit where a and b differ:
- if a.digit(0) == b:
+ adigit = a.digit(0)
+ if adigit == b:
return NULLRBIGINT
- elif a.digit(0) < b:
- sign = -1
- b *= -1
- size_a = size_b = 1
+ elif adigit > b:
+ return rbigint.fromint(adigit - b)
z = rbigint([NULLDIGIT] * size_a, sign, size_a)
borrow = UDIGIT_TYPE(0)
i = _load_unsigned_digit(1)
# The following assumes unsigned arithmetic
# works modulo 2**N for some N>SHIFT.
- borrow = a.udigit(0) - b
+
+ borrow = a.udigit(0) - UDIGIT_TYPE(abs(b))
z.setdigit(0, borrow)
borrow >>= SHIFT
while i < size_a:
@@ -1446,6 +1474,9 @@
#borrow &= 1
i += 1
+ if borrow > 0:
+ print "BORROW IS BAD"
+
assert borrow == 0
z._normalize()
return z
@@ -1505,13 +1536,13 @@
z._normalize()
return z
- elif digit:
+ """elif digit:
if digit & (digit - 1) == 0:
return b.lqshift(ptwotable[digit])
# Even if it's not power of two it can still be useful.
return _muladd1(b, digit)
-
+ """
z = rbigint([NULLDIGIT] * (size_a + size_b), 1)
# gradeschool long mult
i = UDIGIT_TYPE(0)
@@ -1786,6 +1817,9 @@
and the remainder as a tuple.
The sign of a is ignored; n should not be zero.
"""
+ if not (n > 0 and n <= MASK):
+ print "Trying to divide %s by %d" % (a.str(), n)
+
assert n > 0 and n <= MASK
size = a.numdigits()
@@ -1997,6 +2031,10 @@
if b.sign == 0:
raise ZeroDivisionError("long division or modulo by zero")
+ # XXX: Temp
+ if b.sign != 0 and b.numdigits() == 1 and b.digit(0) == 0:
+ print "VERY BAD!"
+
if (size_a < size_b or
(size_a == size_b and
a.digit(abs(size_a-1)) < b.digit(abs(size_b-1)))):
@@ -2540,6 +2578,13 @@
def _int_bitwise(a, op, b): # '&', '|', '^'
""" Bitwise and/or/xor operations with ints. """
+ digit = abs(b)
+ if digit > MASK or not (digit >= 0):
+ # Fallback to long.
+ return _bitwise(a, op, rbigint.fromint(b))
+
+ assert digit >= 0
+
if a.sign < 0:
a = a.invert()
maska = MASK
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
@@ -41,6 +41,30 @@
r2 = r1.neg()
assert r2.str() == str(-n)
+ def test_int_long_catch_div(self):
+ # Basically abs(int) > MASK
+ l = 2**128
+ r1 = rbigint.fromlong(l)
+ assert r1.int_floordiv(-MASK-1).tolong() == (l // (-MASK-1))
+
+ def test_int_long_catch_mul(self):
+ # Basically abs(int) > MASK
+ l = 2**128
+ r1 = rbigint.fromlong(l)
+ assert r1.int_mul(-MASK-1).tolong() == (l * (-MASK-1))
+
+ def test_int_long_catch_add(self):
+ # Basically abs(int) > MASK
+ l = 2**128
+ r1 = rbigint.fromlong(-l)
+ assert r1.int_add(-MASK-1).tolong() == (-l + (-MASK-1))
+
+ def test_int_long_catch_sub(self):
+ # Basically abs(int) > MASK
+ l = 2**128
+ r1 = rbigint.fromlong(-l)
+ assert r1.int_sub(-MASK-1).tolong() == (-l - (-MASK-1))
+
def test_floordiv(self):
for op1 in [-12, -2, -1, 1, 2, 50]:
for op2 in [-4, -2, -1, 1, 2, 8]:
@@ -246,7 +270,7 @@
assert rbigint._from_numberstring_parser(parser).tolong() == 1231231241
def test_add(self):
- x = 123456789123456789000000L
+ x = 123456789123456789000000000000000000L
y = 123858582373821923936744221L
for i in [-1, 1]:
for j in [-1, 1]:
@@ -256,8 +280,8 @@
assert result.tolong() == x * i + y * j
def test_int_add(self):
- x = 123456789123456789000000L
- y = 1238
+ x = 123456789123456789000000000000000000L
+ y = MASK-2
for i in [-1, 1]:
for j in [-1, 1]:
f1 = rbigint.fromlong(x * i)
@@ -278,7 +302,7 @@
def test_int_sub(self):
x = 12378959520302182384345L
- y = 8896
+ y = MASK
for i in [-1, 1]:
for j in [-1, 1]:
f1 = rbigint.fromlong(x * i)
@@ -303,7 +327,7 @@
def test_int_mul(self):
x = -1238585838347L
- y = 585839
+ y = MASK
f1 = rbigint.fromlong(x)
result = f1.int_mul(y)
assert result.tolong() == x * y
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
