Double Dabble
July 31, 2018
Over at ComputerPhile, Professor Brailsford gives a beautiful explanation of the double-dabble algorithm for converting a number from binary to binary-coded decimal. If you don’t want to watch the video — you should — there is also an explanation at Wikipedia, or you can read the original description by C. B. Falconer.
Your task is to implement the double-dabble algorithm as shown by Professor Brailsford. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
That algorithm is obviously nice when implemented in assembler (it uses only one MUTABLE register, it implements a simple and short loop, and foremost, it avoids a costly division by ten).
However, when implement in a high level programming language (EVEN in C!), it is bound to be worse than any other algorithm, because in high level programming languages, numbers are not mutable registers, they are immutable. Therefore manipulating bits in integers is costly! Processing the BCD digits (check if >4 and add 3) n times will be a big waste of time, compared to only (ceilling n 3) divisions by ten!
(defun double-dabble (n w) (let ((b (* 4 (ceiling w 3)))) (flet ((adjust (n) (loop :for p :from w :below (+ w b) :by 4 :for d := (ldb (byte 4 p) n) :when (< 4 d) :do (setf n (dpb (+ 3 d) (byte 4 p) n)) :finally (return n)))) (declare (inline adjust)) (loop :repeat w :do (setf n (ash (adjust n) 1)) :finally (return (ldb (byte b w) n)))))) (defun test/double-dabble () (flet ((check (n) (assert (string= (prin1-to-string n) (format nil "~X" (double-dabble n 16)))))) (check 0) (check 1) (check 10) (check 100) (check 1000) (check 2) (check 20) (check 200) (check 2000) (check 3) (check 30) (check 300) (check 3000) (check 4) (check 40) (check 400) (check 4000) (check 5) (check 50) (check 500) (check 5000) (check 6) (check 60) (check 600) (check 6000) (check 7) (check 70) (check 700) (check 7000) (check 8) (check 80) (check 800) (check 8000) (check 9) (check 90) (check 900) (check 9000) (check 55) (check 5500) (check 1234) (check 4321) (check 99) (check 9900) (check 6789) (check 9876) (check 91) (check 19) (check 9191) (check 1919)) :success) (defun bcd (n w) (let ((b (* 4 (ceiling w 3)))) (loop :with r := 0 :repeat b :for d :from 0 :by 4 :do (multiple-value-bind (q digit) (truncate n 10) (setf r (dpb digit (byte 4 d) r) n q)) :finally (return r)))) (defun test/bcd () (flet ((check (n) (assert (string= (prin1-to-string n) (format nil "~X" (bcd n 16)))))) (check 0) (check 1) (check 10) (check 100) (check 1000) (check 2) (check 20) (check 200) (check 2000) (check 3) (check 30) (check 300) (check 3000) (check 4) (check 40) (check 400) (check 4000) (check 5) (check 50) (check 500) (check 5000) (check 6) (check 60) (check 600) (check 6000) (check 7) (check 70) (check 700) (check 7000) (check 8) (check 80) (check 800) (check 8000) (check 9) (check 90) (check 900) (check 9000) (check 55) (check 5500) (check 1234) (check 4321) (check 99) (check 9900) (check 6789) (check 9876) (check 91) (check 19) (check 9191) (check 1919)) :success) (defun bench/double-dabble () (loop :for i :to 9999 :do (double-dabble i 16))) (defun bench/bcd () (loop :for i :to 9999 :do (bcd i 16))) ;; (load (compile-file #P"~/src/lisp/encours/double-dabble.lisp")) ;; (time (bench/double-dabble)) ;; (time (bench/bcd))On my system double-dabble takes more than double the time of bcd, for 4-digits, 16-bit BCDs.
Here’s a solution in C.
#include <stdint.h> #include <stdio.h> #include <stdlib.h> uint32_t double_dabble(uint32_t n) { uint64_t bcd = n; for (int i = 0; i < 32; ++i) { for (int j = 0; j < 32; j += 4) { if (((bcd >> (32 + j)) & 0x0000000F) > 4) { bcd += ((uint64_t)3 << (32 + j)); } } bcd <<= 1; } bcd >>= 32; return (uint32_t)bcd; } void print_bits(uint32_t n) { for (int i = 31; i >= 0; --i) { printf("%d", (n >> i) & 1); if (i && !(i % 4)) printf(" "); } printf("\n"); } int main(int argc, char* argv[]) { if (argc != 2) { fprintf(stderr, "Usage: %s INT", argv[0]); return EXIT_FAILURE; } uint32_t n = strtoul(argv[1], NULL, 10); uint64_t bcd = double_dabble(n); print_bits(bcd); return EXIT_SUCCESS; }Example:
A good friend died a few years ago. He was very interested in programming microprocessors. The last technical discussion we had was about Double-Dabble. Here an demonstration in Python. So, this one is for Jaques.
from math import ceil def doble(barr): print("shft", end=" ") barr.pop(0) barr.append(9) def print_d(barr, seps): pr = [str(barr[s:s+4]) for s in seps] + [str(barr[seps[-1]+4:])] print("".join(pr)) ADD3 = dict(zip([(0,1,0,1), (0,1,1,0) ,(0,1,1,1), (1,0,0,0), (1,0,0,1)], [(1,0,0,0), (1,0,0,1), (1,0,1,0), (1,0,1,1), (1,1,0,0)])) def add3(barr, seps): for s in seps: b = tuple(barr[s:s+4]) barr[s:s+4] = ADD3.get(b, b) if b != tuple(barr[s:s+4]): print("add3", end=" ") print_d(barr, seps) def ddabble(binary): """ binary: string of 01 """ barr = list(int(i) for i in binary) L = len(barr) dec_nums = ceil(L / 3) barr = [0, 0, 0, 0] * dec_nums + barr seps = list(range(0, dec_nums*4, 4)) print_d(barr, seps) for _ in range(L): add3(barr, seps) doble(barr) print_d(barr, seps) ddabble(bin(288)[2:]) """ [0, 0, 0, 0][0, 0, 0, 0][0, 0, 0, 0][1, 0, 0, 1, 0, 0, 0, 0, 0] shft [0, 0, 0, 0][0, 0, 0, 0][0, 0, 0, 1][0, 0, 1, 0, 0, 0, 0, 0, 9] shft [0, 0, 0, 0][0, 0, 0, 0][0, 0, 1, 0][0, 1, 0, 0, 0, 0, 0, 9, 9] shft [0, 0, 0, 0][0, 0, 0, 0][0, 1, 0, 0][1, 0, 0, 0, 0, 0, 9, 9, 9] shft [0, 0, 0, 0][0, 0, 0, 0][1, 0, 0, 1][0, 0, 0, 0, 0, 9, 9, 9, 9] add3 [0, 0, 0, 0][0, 0, 0, 0][1, 1, 0, 0][0, 0, 0, 0, 0, 9, 9, 9, 9] shft [0, 0, 0, 0][0, 0, 0, 1][1, 0, 0, 0][0, 0, 0, 0, 9, 9, 9, 9, 9] add3 [0, 0, 0, 0][0, 0, 0, 1][1, 0, 1, 1][0, 0, 0, 0, 9, 9, 9, 9, 9] shft [0, 0, 0, 0][0, 0, 1, 1][0, 1, 1, 0][0, 0, 0, 9, 9, 9, 9, 9, 9] add3 [0, 0, 0, 0][0, 0, 1, 1][1, 0, 0, 1][0, 0, 0, 9, 9, 9, 9, 9, 9] shft [0, 0, 0, 0][0, 1, 1, 1][0, 0, 1, 0][0, 0, 9, 9, 9, 9, 9, 9, 9] add3 [0, 0, 0, 0][1, 0, 1, 0][0, 0, 1, 0][0, 0, 9, 9, 9, 9, 9, 9, 9] shft [0, 0, 0, 1][0, 1, 0, 0][0, 1, 0, 0][0, 9, 9, 9, 9, 9, 9, 9, 9] shft [0, 0, 1, 0][1, 0, 0, 0][1, 0, 0, 0][9, 9, 9, 9, 9, 9, 9, 9, 9] """