Schoolbook multiplication in Python
Multiply digit by digit and sum shifted partial products in Theta(n^2) digit operations.
- File
schoolbook_multiplication.py, 60 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/schoolbook-multiplication/. The authors are listed in prov/7VTRV2.jsonl.
def schoolbook_multiply(a: list[int], b: list[int], w: int = 8) -> list[int]:
"""Product of two limb arrays in base 2^w, least significant limb first.
Precondition: each limb is in [0, 2^w). The result has len(a) + len(b) limbs
(the top limb can be 0). Cost: exactly len(a) * len(b) limb products and
Theta(len(a) * len(b)) limb operations.
"""
base = 1 << w
m, n = len(a), len(b)
c = [0] * (m + n) # @line L1
for i in range(m): # @line L2
carry = 0 # @line L3
for j in range(n): # @line L4
t = c[i + j] + a[i] * b[j] + carry # @line L5: t <= base^2 - 1
c[i + j] = t & (base - 1) # @line L6
carry = t >> w # @line L7
c[i + n] = carry # @line L8
return c # @line L9
def schoolbook_square(a: list[int], w: int = 8) -> list[int]:
"""The square of a limb array with n (n - 1) / 2 cross products and n squares.
Each cross product a[i] a[j] with i < j is computed once, the sum of the cross
products is doubled by a shift, and the squares a[i]^2 are added. Cost Theta(n^2).
"""
n = len(a)
cross = [0] * (2 * n)
for i in range(n):
carry = 0
for j in range(i + 1, n):
t = cross[i + j] + a[i] * a[j] + carry
cross[i + j] = t & ((1 << w) - 1)
carry = t >> w
if n:
cross[i + n] = carry
# double the cross products, then add the squares on the diagonal
out = [0] * (2 * n)
carry = 0
for k in range(2 * n):
t = 2 * cross[k] + carry
if k % 2 == 0:
t += a[k // 2] ** 2 % (1 << w)
else:
t += a[k // 2] ** 2 >> w
out[k] = t & ((1 << w) - 1)
carry = t >> w
return out
def multiply_signed(x: tuple[int, list[int]], y: tuple[int, list[int]], w: int = 8) -> tuple[int, list[int]]:
"""Product of (sign, limbs) pairs with sign in {1, -1}, normalized; zero gets sign 1."""
c = schoolbook_multiply(x[1], y[1], w)
while c and c[-1] == 0:
c.pop()
return (x[0] * y[0] if c else 1), c
test_schoolbook_multiplication.py 84 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/schoolbook-multiplication/. The authors are listed in prov/7VTRV2.jsonl.
import random
from schoolbook_multiplication import multiply_signed, schoolbook_multiply, schoolbook_square
def to_limbs(x: int, w: int, n: int | None = None) -> list[int]:
out = []
while x:
out.append(x & ((1 << w) - 1))
x >>= w
if n is not None:
out += [0] * (n - len(out))
return out
def value(c: list[int], w: int) -> int:
v = 0
for d in reversed(c):
v = (v << w) | d
return v
def test_example() -> None:
c = schoolbook_multiply([13, 15, 15], [7, 12], 4)
assert c == [11, 10, 13, 6, 12] and value(c, 4) == 4093 * 199 == 814507
def test_edges() -> None:
w = 4
assert schoolbook_multiply([], [], w) == []
assert schoolbook_multiply([], [3, 4], w) == [0, 0]
assert schoolbook_multiply([0], [15], w) == [0, 0]
assert schoolbook_multiply([1], [9, 9, 9], w) == [9, 9, 9, 0]
assert schoolbook_multiply([15], [15], w) == [1, 14]
for w in (1, 4, 8):
for m in range(1, 6):
for n in range(1, 6):
a, b = [(1 << w) - 1] * m, [(1 << w) - 1] * n
c = schoolbook_multiply(a, b, w)
assert len(c) == m + n
assert value(c, w) == ((1 << (w * m)) - 1) * ((1 << (w * n)) - 1)
def test_very_different_lengths() -> None:
rng = random.Random(5)
for _ in range(50):
a = [rng.randrange(256) for _ in range(rng.randint(40, 80))]
b = [rng.randrange(256)]
assert value(schoolbook_multiply(a, b, 8), 8) == value(a, 8) * value(b, 8)
assert value(schoolbook_multiply(b, a, 8), 8) == value(a, 8) * value(b, 8)
def test_random_against_int() -> None:
rng = random.Random(1962)
for _ in range(1500):
w = rng.choice((1, 2, 4, 8, 16))
m, n = rng.randint(0, 12), rng.randint(0, 12)
x, y = rng.getrandbits(w * m) if m else 0, rng.getrandbits(w * n) if n else 0
a, b = to_limbs(x, w, m), to_limbs(y, w, n)
c = schoolbook_multiply(a, b, w)
assert len(c) == m + n and all(0 <= d < 1 << w for d in c)
assert value(c, w) == x * y
assert value(schoolbook_square(a, w), w) == x * x
def test_square_edges() -> None:
for w in (1, 4, 8):
for n in range(0, 7):
a = [(1 << w) - 1] * n
assert value(schoolbook_square(a, w), w) == value(a, w) ** 2
assert len(schoolbook_square(a, w)) == 2 * n
def test_signed() -> None:
rng = random.Random(9)
for _ in range(500):
x, y = rng.randint(-5000, 5000), rng.randint(-5000, 5000)
sx, sy = (1 if x >= 0 else -1), (1 if y >= 0 else -1)
s, c = multiply_signed((sx, to_limbs(abs(x), 4)), (sy, to_limbs(abs(y), 4)), 4)
assert s * value(c, 4) == x * y
assert (not c and s == 1) or c[-1] != 0
What the next level needs
- the tests did not run in this build