Double dabble algorithm demo in Python

dd_bcd.py

#!/usr/bin/env python3

# MIT License, Witold Baryluk, 2022

# double dabble algorithm for convering binary numbers to decimal notation.
# This is program is not for speed, but just for ilustration and education.
# It works, and could be starting point to trying to understand
# how it works, and implement it for example on a microcontroller without
# division.

# x = 243
x = 65244
# x = 4294967185
# x = 348199535390660743


digits = len(str(x))
width = len(bin(x)) - 2


scratch = [0] * (digits * 4)

word_size = 8  # for computing shift_count
shift_count = 0  # number of word-bit shifts

x0 = x

print(
    f"Will convert {width}-bit value 0b{x:b} to decimal (expecting end result: {x0} with {digits} digits)"
)
print()


def shift_scratch(new_lsb=0):
    global scratch, shift_count
    print("shift")
    shift_count += (len(scratch) + 4) // word_size
    scratch = scratch[1:] + [new_lsb]


def scratch_digit_read(j):
    return (
        (scratch[4 * j] << 3)
        + (scratch[4 * j + 1] << 2)
        + (scratch[4 * j + 2] << 1)
        + (scratch[4 * j + 3])
    )


def scratch_digit_write(j, x):
    global scratch
    assert 0 <= x and x <= 0xF
    # assert 0 <= x and x <= 9
    scratch[4 * j + 0] = x >> 3
    scratch[4 * j + 1] = (x >> 2) & 1
    scratch[4 * j + 2] = (x >> 1) & 1
    scratch[4 * j + 3] = x & 1


def extract_msb(x):
    return (x >> (width - 1)) & 1


def shift_x():
    global x, shift_count
    shift_count += (width + 7) // word_size
    x = (x << 1) & ((1 << width) - 1)


def dump(show_ups=False, end=" "):
    print("Bin:", end="")
    for i in range(digits):
        print(f" {scratch_digit_read(i):04b}", end="")
    print(f"  {x:0{width}b}")
    print("Dec:", end="")
    for i in range(digits):
        print(f" {scratch_digit_read(i):4d}", end="")
    print()
    print("    ", end="")
    if show_ups:
        for i in range(digits):
            if scratch_digit_read(i) >= 5:
                print(f"    ^", end="")
            else:
                print(f"     ", end="")
    print()


def dd():
    global x
    dump()

    for i in range(3):
        shift_scratch(extract_msb(x))
        print(shift_count)
        shift_x()
        print(shift_count)
        dump(show_ups=(i == 2))

    for i in range(width - 3):
        print("checking if need to add")
        for j in range(digits):
            digit = scratch_digit_read(j)
            power = f"10^{digits-j-1}"
            print(f"digit at position {j:2d} ({power:5}): {digit:2}", end=" : ")
            if digit >= 5:
                digit += 3
                print(f"need to add,    result:  {digit:2d}")
                # assert 0 <= digit and digit <= 9
                scratch_digit_write(j, digit)
            else:
                print(f"no need to add, keeping: {digit:2d}")
        dump(show_ups=False)
        shift_scratch(extract_msb(x))
        print(shift_count)
        shift_x()
        print(shift_count)
        dump(show_ups=(i < width - 4))

    print("Final decimal result:", end="")
    got = 0
    for i in range(digits):
        digit = scratch_digit_read(i)
        print(f" {digit:d}", end="")
        got = 10 * got + digit
    print()
    assert got == x0
    print(f"Final result is same as expected from the start ({x0})")


if __name__ == "__main__":
    dd()
    print(f"Total number of {word_size}-bit shifts:", shift_count)

Example output:

Will convert 16-bit value 0b1111111011011100 to decimal (expecting end result: 65244 with 5 digits)

Bin: 0000 0000 0000 0000 0000  1111111011011100
Dec:    0    0    0    0    0
    
shift
3
5
Bin: 0000 0000 0000 0000 0001  1111110110111000
Dec:    0    0    0    0    1
    
shift
8
10
Bin: 0000 0000 0000 0000 0011  1111101101110000
Dec:    0    0    0    0    3
    
shift
13
15
Bin: 0000 0000 0000 0000 0111  1111011011100000
Dec:    0    0    0    0    7
                            ^
checking if need to add
digit at position  0 (10^4 ):  0 : no need to add, keeping:  0
digit at position  1 (10^3 ):  0 : no need to add, keeping:  0
digit at position  2 (10^2 ):  0 : no need to add, keeping:  0
digit at position  3 (10^1 ):  0 : no need to add, keeping:  0
digit at position  4 (10^0 ):  7 : need to add,    result:  10
Bin: 0000 0000 0000 0000 1010  1111011011100000
Dec:    0    0    0    0   10
    
shift
18
20
Bin: 0000 0000 0000 0001 0101  1110110111000000
Dec:    0    0    0    1    5
                            ^
checking if need to add
digit at position  0 (10^4 ):  0 : no need to add, keeping:  0
digit at position  1 (10^3 ):  0 : no need to add, keeping:  0
digit at position  2 (10^2 ):  0 : no need to add, keeping:  0
digit at position  3 (10^1 ):  1 : no need to add, keeping:  1
digit at position  4 (10^0 ):  5 : need to add,    result:   8
Bin: 0000 0000 0000 0001 1000  1110110111000000
Dec:    0    0    0    1    8
    
shift
23
25
Bin: 0000 0000 0000 0011 0001  1101101110000000
Dec:    0    0    0    3    1
                             
checking if need to add
digit at position  0 (10^4 ):  0 : no need to add, keeping:  0
digit at position  1 (10^3 ):  0 : no need to add, keeping:  0
digit at position  2 (10^2 ):  0 : no need to add, keeping:  0
digit at position  3 (10^1 ):  3 : no need to add, keeping:  3
digit at position  4 (10^0 ):  1 : no need to add, keeping:  1
Bin: 0000 0000 0000 0011 0001  1101101110000000
Dec:    0    0    0    3    1
    
shift
28
30
Bin: 0000 0000 0000 0110 0011  1011011100000000
Dec:    0    0    0    6    3
                       ^     
checking if need to add
digit at position  0 (10^4 ):  0 : no need to add, keeping:  0
digit at position  1 (10^3 ):  0 : no need to add, keeping:  0
digit at position  2 (10^2 ):  0 : no need to add, keeping:  0
digit at position  3 (10^1 ):  6 : need to add,    result:   9
digit at position  4 (10^0 ):  3 : no need to add, keeping:  3
Bin: 0000 0000 0000 1001 0011  1011011100000000
Dec:    0    0    0    9    3
    
shift
33
35
Bin: 0000 0000 0001 0010 0111  0110111000000000
Dec:    0    0    1    2    7
                            ^
checking if need to add
digit at position  0 (10^4 ):  0 : no need to add, keeping:  0
digit at position  1 (10^3 ):  0 : no need to add, keeping:  0
digit at position  2 (10^2 ):  1 : no need to add, keeping:  1
digit at position  3 (10^1 ):  2 : no need to add, keeping:  2
digit at position  4 (10^0 ):  7 : need to add,    result:  10
Bin: 0000 0000 0001 0010 1010  0110111000000000
Dec:    0    0    1    2   10
    
shift
38
40
Bin: 0000 0000 0010 0101 0100  1101110000000000
Dec:    0    0    2    5    4
                       ^     
checking if need to add
digit at position  0 (10^4 ):  0 : no need to add, keeping:  0
digit at position  1 (10^3 ):  0 : no need to add, keeping:  0
digit at position  2 (10^2 ):  2 : no need to add, keeping:  2
digit at position  3 (10^1 ):  5 : need to add,    result:   8
digit at position  4 (10^0 ):  4 : no need to add, keeping:  4
Bin: 0000 0000 0010 1000 0100  1101110000000000
Dec:    0    0    2    8    4
    
shift
43
45
Bin: 0000 0000 0101 0000 1001  1011100000000000
Dec:    0    0    5    0    9
                  ^         ^
checking if need to add
digit at position  0 (10^4 ):  0 : no need to add, keeping:  0
digit at position  1 (10^3 ):  0 : no need to add, keeping:  0
digit at position  2 (10^2 ):  5 : need to add,    result:   8
digit at position  3 (10^1 ):  0 : no need to add, keeping:  0
digit at position  4 (10^0 ):  9 : need to add,    result:  12
Bin: 0000 0000 1000 0000 1100  1011100000000000
Dec:    0    0    8    0   12
    
shift
48
50
Bin: 0000 0001 0000 0001 1001  0111000000000000
Dec:    0    1    0    1    9
                            ^
checking if need to add
digit at position  0 (10^4 ):  0 : no need to add, keeping:  0
digit at position  1 (10^3 ):  1 : no need to add, keeping:  1
digit at position  2 (10^2 ):  0 : no need to add, keeping:  0
digit at position  3 (10^1 ):  1 : no need to add, keeping:  1
digit at position  4 (10^0 ):  9 : need to add,    result:  12
Bin: 0000 0001 0000 0001 1100  0111000000000000
Dec:    0    1    0    1   12
    
shift
53
55
Bin: 0000 0010 0000 0011 1000  1110000000000000
Dec:    0    2    0    3    8
                            ^
checking if need to add
digit at position  0 (10^4 ):  0 : no need to add, keeping:  0
digit at position  1 (10^3 ):  2 : no need to add, keeping:  2
digit at position  2 (10^2 ):  0 : no need to add, keeping:  0
digit at position  3 (10^1 ):  3 : no need to add, keeping:  3
digit at position  4 (10^0 ):  8 : need to add,    result:  11
Bin: 0000 0010 0000 0011 1011  1110000000000000
Dec:    0    2    0    3   11
    
shift
58
60
Bin: 0000 0100 0000 0111 0111  1100000000000000
Dec:    0    4    0    7    7
                       ^    ^
checking if need to add
digit at position  0 (10^4 ):  0 : no need to add, keeping:  0
digit at position  1 (10^3 ):  4 : no need to add, keeping:  4
digit at position  2 (10^2 ):  0 : no need to add, keeping:  0
digit at position  3 (10^1 ):  7 : need to add,    result:  10
digit at position  4 (10^0 ):  7 : need to add,    result:  10
Bin: 0000 0100 0000 1010 1010  1100000000000000
Dec:    0    4    0   10   10
    
shift
63
65
Bin: 0000 1000 0001 0101 0101  1000000000000000
Dec:    0    8    1    5    5
             ^         ^    ^
checking if need to add
digit at position  0 (10^4 ):  0 : no need to add, keeping:  0
digit at position  1 (10^3 ):  8 : need to add,    result:  11
digit at position  2 (10^2 ):  1 : no need to add, keeping:  1
digit at position  3 (10^1 ):  5 : need to add,    result:   8
digit at position  4 (10^0 ):  5 : need to add,    result:   8
Bin: 0000 1011 0001 1000 1000  1000000000000000
Dec:    0   11    1    8    8
    
shift
68
70
Bin: 0001 0110 0011 0001 0001  0000000000000000
Dec:    1    6    3    1    1
             ^               
checking if need to add
digit at position  0 (10^4 ):  1 : no need to add, keeping:  1
digit at position  1 (10^3 ):  6 : need to add,    result:   9
digit at position  2 (10^2 ):  3 : no need to add, keeping:  3
digit at position  3 (10^1 ):  1 : no need to add, keeping:  1
digit at position  4 (10^0 ):  1 : no need to add, keeping:  1
Bin: 0001 1001 0011 0001 0001  0000000000000000
Dec:    1    9    3    1    1
    
shift
73
75
Bin: 0011 0010 0110 0010 0010  0000000000000000
Dec:    3    2    6    2    2
                  ^          
checking if need to add
digit at position  0 (10^4 ):  3 : no need to add, keeping:  3
digit at position  1 (10^3 ):  2 : no need to add, keeping:  2
digit at position  2 (10^2 ):  6 : need to add,    result:   9
digit at position  3 (10^1 ):  2 : no need to add, keeping:  2
digit at position  4 (10^0 ):  2 : no need to add, keeping:  2
Bin: 0011 0010 1001 0010 0010  0000000000000000
Dec:    3    2    9    2    2
    
shift
78
80
Bin: 0110 0101 0010 0100 0100  0000000000000000
Dec:    6    5    2    4    4
    
Final decimal result: 6 5 2 4 4
Final result is same as expected from the start (65244)
Total number of 8-bit shifts: 80