Double dabble in Python
Converts binary to packed BCD by shifting left and adding 3 to digits of 5 or more.
- File
double_dabble.py, 38 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/double-dabble/. The authors are listed in prov/8H3YQ9.jsonl.
def decimal_digits_for(n: int) -> int:
"""The number of decimal digits of 2^n - 1, enough for any n-bit number."""
return max(1, len(str((1 << n) - 1)))
def double_dabble(bits: list[int]) -> list[int]:
"""Convert a binary number to BCD digits by shift and add 3.
Precondition: bits holds n >= 0 entries in {0, 1}, the most significant
bit first. Returns d = decimal_digits_for(n) BCD digits, the least
significant digit first, each in 0..9. Cost: n * d digit steps, each a
compare, an add of 3 and a shift of a 4-bit digit, so Theta(n^2).
"""
n = len(bits)
d = decimal_digits_for(n)
digits = [0] * d # @line L1
for bit in bits: # @line L2
for i in range(d): # @line L3
if digits[i] >= 5: # @line L4
digits[i] += 3
carry = bit # @line L5
for i in range(d): # @line L6
t = 2 * digits[i] + carry # @line L7
digits[i], carry = t & 15, t >> 4 # @line L8
if carry:
raise AssertionError("the BCD register overflowed")
return digits # @line L9
def to_bcd(x: int, n: int) -> int:
"""The packed BCD form of 0 <= x < 2^n: four bits per decimal digit."""
bits = [(x >> k) & 1 for k in range(n - 1, -1, -1)]
digits = double_dabble(bits)
return sum(dig << (4 * i) for i, dig in enumerate(digits))
test_double_dabble.py 64 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/double-dabble/. The authors are listed in prov/8H3YQ9.jsonl.
import random
from double_dabble import decimal_digits_for, double_dabble, to_bcd
def bits_of(x: int, n: int) -> list[int]:
return [(x >> k) & 1 for k in range(n - 1, -1, -1)]
def reference_bcd(x: int) -> int:
"""Packed BCD by reading the decimal string, an independent oracle."""
return int(str(x), 16)
def test_example() -> None:
assert double_dabble([1, 1, 1, 1, 0, 0, 1, 1]) == [3, 4, 2]
assert to_bcd(243, 8) == 0x243
assert to_bcd(65535, 16) == 0x65535
def test_digit_count() -> None:
assert decimal_digits_for(0) == 1
assert decimal_digits_for(8) == 3
assert decimal_digits_for(16) == 5
for n in range(1, 200):
assert decimal_digits_for(n) == len(str(2**n - 1))
def test_edges() -> None:
assert double_dabble([]) == [0]
assert double_dabble([0]) == [0]
assert double_dabble([1]) == [1]
for n in (1, 3, 4, 7, 8, 10, 64, 100):
top = (1 << n) - 1
assert to_bcd(top, n) == reference_bcd(top)
assert to_bcd(0, n) == 0
assert to_bcd(1 << (n - 1), n) == reference_bcd(1 << (n - 1))
def test_exhaustive_small() -> None:
for n in range(1, 13):
for x in range(1 << n):
digits = double_dabble(bits_of(x, n))
assert all(0 <= v <= 9 for v in digits)
assert sum(v * 10**i for i, v in enumerate(digits)) == x
def test_powers_of_ten() -> None:
for e in range(0, 30):
x = 10**e
n = x.bit_length()
assert to_bcd(x, n) == reference_bcd(x)
assert to_bcd(x - 1, n) == reference_bcd(x - 1)
def test_random_against_str() -> None:
rng = random.Random(1243)
for _ in range(500):
n = rng.randint(1, 300)
x = rng.randrange(1 << n)
assert to_bcd(x, n) == reference_bcd(x)
What the next level needs
- the tests did not run in this build