Brent-Kung adder in Python
Parallel-prefix adder with fewer prefix cells and about twice the depth of Kogge-Stone.
- File
brent_kung_adder.py, 97 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/brent-kung-adder/. The authors are listed in prov/XD1FWT.jsonl.
"""The Brent-Kung parallel-prefix adder, simulated gate by gate.
Bit lists are least significant bit first. Every signal is a pair (value,
arrival time), every gate has two inputs and unit delay, and the simulation
counts gates, prefix cells and the levels of cells that are not empty, so
that the tests can check the size and depth claims of the page.
"""
from dataclasses import dataclass
Wire = tuple[int, int]
@dataclass
class Stats:
gates: int = 0
cells: int = 0
levels: int = 0
def _gate(op, x: Wire, y: Wire, st: Stats) -> Wire:
st.gates += 1
return op(x[0], y[0]), max(x[1], y[1]) + 1
def _and(x: Wire, y: Wire, st: Stats) -> Wire:
return _gate(lambda u, v: u & v, x, y, st)
def _or(x: Wire, y: Wire, st: Stats) -> Wire:
return _gate(lambda u, v: u | v, x, y, st)
def _xor(x: Wire, y: Wire, st: Stats) -> Wire:
return _gate(lambda u, v: u ^ v, x, y, st)
def _combine(G, P, lo, i, j, st: Stats) -> None:
"""(G, P)[i] <- (G, P)[i] o (G, P)[j], where j is the position just below the block of i."""
G[i] = _or(G[i], _and(P[i], G[j], st), st)
if lo[j] > 0: # the new block does not reach position 0, so its P is still needed
P[i] = _and(P[i], P[j], st)
lo[i] = lo[j]
st.cells += 1
def brent_kung_add(a: list[int], b: list[int], c_in: int = 0, st: Stats | None = None) -> tuple[list[int], int]:
"""Add two n-bit lists; return the n + 1 result bits (carry out last) and the depth."""
if st is None:
st = Stats()
n = len(a)
if len(b) != n or n == 0:
raise ValueError("the operands must have the same positive width")
cin = (c_in & 1, 0)
A = [(x & 1, 0) for x in a]
B = [(x & 1, 0) for x in b]
g = [_and(A[i], B[i], st) for i in range(n)] # @line L1
p = [_xor(A[i], B[i], st) for i in range(n)] # @line L1
g[0] = _or(g[0], _and(p[0], cin, st), st) # @line L2
G, P = list(g), list(p) # @line L3
lo = list(range(n)) # lo[i]: the lowest position of the block held by i
d = 1 # @line L3
while d < n: # @line L4
level = range(2 * d - 1, n, 2 * d)
for i in level: # @line L5
_combine(G, P, lo, i, i - d, st)
st.levels += len(level) > 0
d *= 2 # @line L6
d //= 4 # @line L7
while d >= 1: # @line L8
level = range(3 * d - 1, n, 2 * d)
for i in level: # @line L9
_combine(G, P, lo, i, i - d, st)
st.levels += len(level) > 0
d //= 2 # @line L10
assert all(x == 0 for x in lo)
c = [cin] + G # @line L11
s = [_xor(p[i], c[i], st) for i in range(n)] # @line L12
out = s + [c[n]]
return [x[0] for x in out], max(x[1] for x in out) # @line L13
def to_bits(x: int, n: int) -> list[int]:
return [(x >> i) & 1 for i in range(n)]
def from_bits(bits: list[int]) -> int:
return sum(bit << i for i, bit in enumerate(bits))
def add(x: int, y: int, n: int, c_in: int = 0) -> int:
"""x + y + c_in for 0 <= x, y < 2^n, through the circuit."""
bits, _ = brent_kung_add(to_bits(x, n), to_bits(y, n), c_in)
return from_bits(bits)
test_brent_kung_adder.py 66 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/brent-kung-adder/. The authors are listed in prov/XD1FWT.jsonl.
import random
from brent_kung_adder import Stats, add, brent_kung_add, from_bits, to_bits
def _expected_levels(n: int) -> int:
up = n.bit_length() - 1
down = (n // 3).bit_length() if n >= 3 else 0
return up + down
def test_example() -> None:
st = Stats()
bits, depth = brent_kung_add(to_bits(182, 8), to_bits(91, 8), 0, st)
assert from_bits(bits) == 273
assert st.cells == 11 and st.levels == 5 and depth == 12
def test_exhaustive_small() -> None:
for n in range(1, 7):
for x in range(1 << n):
for y in range(1 << n):
for c in (0, 1):
assert add(x, y, n, c) == x + y + c
def test_edges() -> None:
for n in (1, 2, 3, 7, 8, 9, 31, 32, 33, 64, 100):
top = (1 << n) - 1
assert add(0, 0, n) == 0
assert add(top, 0, n, 1) == 1 << n
assert add(top, 1, n) == 1 << n
assert add(top, top, n, 1) == 2 * top + 1
alt = int("10" * n, 2) & top
assert add(alt, top ^ alt, n, 1) == 1 << n
def test_random() -> None:
rng = random.Random(1982)
for _ in range(800):
n = rng.randint(1, 120)
x, y, c = rng.getrandbits(n), rng.getrandbits(n), rng.randint(0, 1)
assert add(x, y, n, c) == x + y + c
def test_cells_levels_depth() -> None:
for n in range(1, 300):
st = Stats()
_, depth = brent_kung_add([1] * n, [0] * n, 1, st)
floor_log = n.bit_length() - 1
assert st.cells == 2 * n - 1 - bin(n).count("1") - floor_log
assert st.levels == _expected_levels(n)
assert depth <= 2 * st.levels + 4
def test_powers_of_two() -> None:
for L in range(2, 11):
n = 1 << L
st = Stats()
_, depth = brent_kung_add([1] * n, [0] * n, 1, st)
assert st.cells == 2 * n - 2 - L
assert st.levels == 2 * L - 1
assert depth == 4 * L
What the next level needs
- the tests did not run in this build