Author: Amaury Forgeot d'Arc <[email protected]>
Branch:
Changeset: r59205:4d9071d3ecb4
Date: 2012-12-02 00:29 +0100
http://bitbucket.org/pypy/pypy/changeset/4d9071d3ecb4/
Log: Remove extra copy of _x_mul
diff --git a/pypy/rlib/rbigint.py b/pypy/rlib/rbigint.py
--- a/pypy/rlib/rbigint.py
+++ b/pypy/rlib/rbigint.py
@@ -1122,85 +1122,6 @@
z._normalize()
return z
-def _x_mul(a, b, digit=0):
- """
- Grade school multiplication, ignoring the signs.
- Returns the absolute value of the product, or None if error.
- """
-
- size_a = a.numdigits()
- 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 = UDIGIT_TYPE(0)
- while i < size_a:
- f = a.widedigit(i)
- pz = i << 1
- pa = i + 1
-
- carry = z.widedigit(pz) + f * f
- z.setdigit(pz, carry)
- pz += 1
- carry >>= SHIFT
- assert carry <= MASK
-
- # Now f is added in twice in each column of the
- # pyramid it appears. Same as adding f<<1 once.
- f <<= 1
- while pa < size_a:
- carry += z.widedigit(pz) + a.widedigit(pa) * f
- pa += 1
- z.setdigit(pz, carry)
- pz += 1
- carry >>= SHIFT
- if carry:
- carry += z.widedigit(pz)
- z.setdigit(pz, carry)
- pz += 1
- carry >>= SHIFT
- if carry:
- z.setdigit(pz, z.widedigit(pz) + carry)
- assert (carry >> SHIFT) == 0
- i += 1
- z._normalize()
- return z
-
- 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)
- 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:
- assert pz >= 0
- z.setdigit(pz, z.widedigit(pz) + carry)
- assert (carry >> SHIFT) == 0
- i += 1
- z._normalize()
- return z
-
def _kmul_split(n, size):
"""
A helper for Karatsuba multiplication (k_mul).
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
