Ripple-carry adder in Python
Chains full adders so each carry feeds the next, taking time linear in the word length.
- File
ripple_carry_adder.py, 92 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/ripple-carry-adder/. The authors are listed in prov/0BHM0W.jsonl.
def full_adder(a: int, b: int, c: int) -> tuple[int, int]:
"""One full adder cell on bits: returns (sum, carry out) with a + b + c = sum + 2 carry."""
p = a ^ b
return p ^ c, (a & b) | (c & p)
def ripple_carry_add(a: list[int], b: list[int], c_in: int = 0) -> list[int]:
"""Sum of two n-bit words, least significant bit first, as n + 1 bits.
The circuit is a chain of n full adders. Each stage uses the gates
p = a XOR b, g = a AND b, s = p XOR c, c' = g OR (p AND c): 5 gates, so 5n gates,
and the carry passes through 2 gates per stage, so the depth is 2n + 1.
"""
if len(a) != len(b):
raise ValueError("operands must have the same width")
n = len(a)
s = [0] * (n + 1)
c = c_in # @line L1
for i in range(n): # @line L2
p = a[i] ^ b[i] # @line L3
g = a[i] & b[i] # @line L4
s[i] = p ^ c # @line L5
c = g | (p & c) # @line L6
s[n] = c # @line L7
return s # @line L8
def ripple_carry_add_limbs(a: list[int], b: list[int], w: int = 8, c_in: int = 0) -> list[int]:
"""The same chain in radix 2^w: each cell adds two limbs and a carry bit.
This is the multiprecision addition of the word RAM (Knuth's Algorithm A).
"""
if len(a) != len(b):
raise ValueError("operands must have the same length")
mask = (1 << w) - 1
s = [0] * (len(a) + 1)
c = c_in
for i in range(len(a)):
t = a[i] + b[i] + c
s[i] = t & mask
c = t >> w
s[len(a)] = c
return s
def add_signed(a: list[int], b: list[int]) -> tuple[list[int], int]:
"""Two's complement addition of n-bit words: the n-bit sum and the overflow flag.
The overflow flag is the XOR of the carry into and the carry out of the top stage.
"""
n = len(a)
if n != len(b) or n == 0:
raise ValueError("operands must have the same positive width")
c = 0
s = [0] * n
c_top_in = 0
for i in range(n):
if i == n - 1:
c_top_in = c
s[i], c = full_adder(a[i], b[i], c)
return s, c_top_in ^ c
def subtract(a: list[int], b: list[int]) -> tuple[list[int], int]:
"""a - b modulo 2^n by a + NOT b + 1; returns the n-bit difference and the carry out.
The carry out is 1 exactly when a >= b as unsigned numbers (no borrow).
"""
s = ripple_carry_add(a, [1 - x for x in b], 1)
return s[:-1], s[-1]
def carry_chain_length(a: list[int], b: list[int]) -> int:
"""The longest run of stages through which one carry propagates (the settling time).
A carry is generated at stage i (a_i = b_i = 1) and travels while p_j = 1.
"""
longest = run = 0
active = False
for x, y in zip(a, b):
if x & y:
active, run = True, 1
elif x ^ y and active:
run += 1
else:
active, run = False, 0
longest = max(longest, run)
return longest
test_ripple_carry_adder.py 100 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/ripple-carry-adder/. The authors are listed in prov/0BHM0W.jsonl.
import random
from ripple_carry_adder import (
add_signed,
carry_chain_length,
full_adder,
ripple_carry_add,
ripple_carry_add_limbs,
subtract,
)
def bits(x: int, n: int) -> list[int]:
return [(x >> i) & 1 for i in range(n)]
def limbs(x: int, w: int, n: int) -> list[int]:
return [(x >> (w * i)) & ((1 << w) - 1) for i in range(n)]
def value(d: list[int], w: int = 1) -> int:
v = 0
for x in reversed(d):
v = (v << w) | x
return v
def signed(d: list[int]) -> int:
v = value(d)
return v - (1 << len(d)) if d and d[-1] else v
def test_full_adder_truth_table() -> None:
for a in (0, 1):
for b in (0, 1):
for c in (0, 1):
s, co = full_adder(a, b, c)
assert s + 2 * co == a + b + c
def test_example() -> None:
s = ripple_carry_add(bits(11, 4), bits(6, 4))
assert s == [1, 0, 0, 0, 1] and value(s) == 17
assert carry_chain_length(bits(11, 4), bits(6, 4)) == 3
def test_edges_bits() -> None:
for n in (1, 2, 8, 33):
top = (1 << n) - 1
for x, y, c in [(0, 0, 0), (0, 0, 1), (1, 0, 0), (top, 0, 1), (top, 1, 0), (top, top, 1), (top, top, 0)]:
x &= top
y &= top
assert value(ripple_carry_add(bits(x, n), bits(y, n), c)) == x + y + c
# the longest carry chain: all ones plus one
assert carry_chain_length(bits(255, 8), bits(1, 8)) == 8
assert ripple_carry_add([], []) == [0]
def test_random_bits() -> None:
rng = random.Random(4096)
for _ in range(3000):
n = rng.randint(1, 70)
x, y, c = rng.getrandbits(n), rng.getrandbits(n), rng.randint(0, 1)
assert value(ripple_carry_add(bits(x, n), bits(y, n), c)) == x + y + c
def test_limbs() -> None:
rng = random.Random(1946)
for w in (4, 8):
base = 1 << w
top = base - 1
cases = [(0, 0, 1), (1, 1, 1), (top, 1, 1), (top, top, 1), (base**5 - 1, 1, 5), (base**5 - 1, base**5 - 1, 5)]
for x, y, n in cases:
assert value(ripple_carry_add_limbs(limbs(x, w, n), limbs(y, w, n), w), w) == x + y
for _ in range(1500):
n = rng.randint(1, 20)
x, y = rng.getrandbits(w * n), rng.getrandbits(w * n)
if rng.random() < 0.2:
x = base**n - 1
s = ripple_carry_add_limbs(limbs(x, w, n), limbs(y, w, n), w)
assert len(s) == n + 1 and value(s, w) == x + y
def test_signed_and_subtract() -> None:
for n in (1, 2, 3, 4, 8):
lo, hi = -(1 << (n - 1)), (1 << (n - 1)) - 1
for x in range(lo, hi + 1):
for y in range(lo, hi + 1):
s, ov = add_signed(bits(x, n), bits(y, n))
exact = x + y
assert ov == (not lo <= exact <= hi)
assert (signed(s) - exact) % (1 << n) == 0
for n in (1, 4, 8):
for x in range(1 << n):
for y in range(1 << n):
d, c = subtract(bits(x, n), bits(y, n))
assert value(d) == (x - y) % (1 << n) and c == (1 if x >= y else 0)
What the next level needs
- the tests did not run in this build