Russian peasant multiplication in Python
Multiply by repeated doubling and halving, using only addition and bit shifts.
- File
russian_peasant_multiplication.py, 61 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/russian-peasant-multiplication/. The authors are listed in prov/ANVYVS.jsonl.
def russian_peasant_multiply(x: list[int], y: list[int], w: int = 8) -> list[int]:
"""Product of two nonnegative limb arrays (base 2^w, least significant limb first).
Halve y and double x until y is zero, and add x to the result whenever y is
odd. Uses only addition and one-bit shifts. Returns a normalized limb array.
Cost: O(N) additions and shifts of arrays of O(n) limbs, where N is the
number of binary digits of y, so O(N (m + n)) limb operations.
"""
p: list[int] = [] # @line L1
x, y = _normalize(list(x)), _normalize(list(y))
while y: # @line L2: y > 0
if y[0] & 1: # @line L3
p = _add(p, x, w)
x = _shl1(x, w) # @line L4
y = _shr1(y, w) # @line L5
return p # @line L6
def _normalize(a: list[int]) -> list[int]:
while a and a[-1] == 0:
a.pop()
return a
def _add(a: list[int], b: list[int], w: int) -> list[int]:
"""a + b for limb arrays, one carry pass."""
if len(a) < len(b):
a, b = b, a
out, carry, mask = [], 0, (1 << w) - 1
for i in range(len(a)):
t = a[i] + (b[i] if i < len(b) else 0) + carry
out.append(t & mask)
carry = t >> w
if carry:
out.append(carry)
return out
def _shl1(a: list[int], w: int) -> list[int]:
"""2 a: shift each limb left by one bit and pass the top bit up."""
out, carry, mask = [], 0, (1 << w) - 1
for d in a:
out.append(((d << 1) & mask) | carry)
carry = d >> (w - 1)
if carry:
out.append(carry)
return out
def _shr1(a: list[int], w: int) -> list[int]:
"""floor(a / 2): shift each limb right by one bit and pass the low bit down."""
out = [0] * len(a)
carry = 0
for i in range(len(a) - 1, -1, -1):
out[i] = (a[i] >> 1) | (carry << (w - 1))
carry = a[i] & 1
return _normalize(out)
test_russian_peasant_multiplication.py 61 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/russian-peasant-multiplication/. The authors are listed in prov/ANVYVS.jsonl.
import random
from russian_peasant_multiplication import russian_peasant_multiply
def limbs(x: int, w: int) -> list[int]:
out = []
while x:
out.append(x & ((1 << w) - 1))
x >>= w
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:
assert value(russian_peasant_multiply(limbs(4093, 4), limbs(199, 4), 4), 4) == 814507
def test_edges() -> None:
for w in (1, 4, 8):
top = (1 << w) - 1
assert russian_peasant_multiply([], [], w) == []
assert russian_peasant_multiply([], [1], w) == []
assert russian_peasant_multiply([5 % (1 << w)], [], w) == []
assert russian_peasant_multiply([0, 0], [1], w) == []
assert russian_peasant_multiply([1], [1], w) == [1]
assert russian_peasant_multiply([top] * 3, [1], w) == [top] * 3
for m in range(1, 5):
for n in range(1, 5):
x, y = (1 << (w * m)) - 1, (1 << (w * n)) - 1
r = russian_peasant_multiply(limbs(x, w), limbs(y, w), w)
assert value(r, w) == x * y and r[-1] != 0
# a carry into a new limb on doubling
assert value(russian_peasant_multiply([top], [2], w), w) == 2 * top
def test_very_different_lengths() -> None:
rng = random.Random(11)
for _ in range(40):
x, y = rng.getrandbits(400), rng.randrange(1, 256)
assert value(russian_peasant_multiply(limbs(x, 8), limbs(y, 8), 8), 8) == x * y
assert value(russian_peasant_multiply(limbs(y, 8), limbs(x, 8), 8), 8) == x * y
def test_random_against_int() -> None:
rng = random.Random(1650)
for _ in range(1200):
w = rng.choice((1, 2, 4, 8))
x, y = rng.getrandbits(rng.randint(0, 64)), rng.getrandbits(rng.randint(0, 64))
r = russian_peasant_multiply(limbs(x, w), limbs(y, w), w)
assert value(r, w) == x * y
assert all(0 <= d < 1 << w for d in r) and (not r or r[-1] != 0)
What the next level needs
- the tests did not run in this build