# Commits

committed 4d9071d

Remove extra copy of _x_mul

• Participants
• Parent commits a3c1766
• Branches default

# File pypy/rlib/rbigint.py

`     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).`