Double Dabble
July 31, 2018
We store the “scratch register” and the original number together in a single bitstring, initially n the number to be converted, then gradually build up the binary-coded decimal representation in the most-significant bits of n:
(define (dabble-ones n)
(let ((ones (modulo (quotient n (* 16 16)) 16)))
(cond ((< 4 ones)
(display " dabble-ones")
(+ n (* 3 (* 16 16))))
(else n))))
(define (dabble-tens n)
(let ((tens (modulo (quotient n (* 16 16 16)) 16)))
(cond ((< 4 tens)
(display " dabble-tens")
(+ n (* 3 (* 16 16 16))))
(else n))))
(define (double-dabble n)
(do ((i 0 (+ i 1)))
((= i 8) (display (display-bits n)) (newline))
(display (display-bits n))
(set! n (dabble-ones n))
(set! n (dabble-tens n))
(set! n (double n))
(newline)))
The two dabble procedures extract the desired bits from the bitstring and add 3 if needed; the double procedure works unconditionally. Display-bits uses some Common Lisp hackery:
(define (display-bits n)
(string-join #\space (list
(format "~4,'0B" (modulo (quotient n (* 16 16 16 16)) 16))
(format "~4,'0B" (modulo (quotient n (* 16 16 16)) 16))
(format "~4,'0B" (modulo (quotient n (* 16 16)) 16))
(format "~8,'0B" (modulo n 256)))))
Here are some examples:
> (double-dabble 42) 0000 0000 0000 00101010 0000 0000 0000 01010100 0000 0000 0000 10101000 0000 0000 0001 01010000 0000 0000 0010 10100000 0000 0000 0101 01000000 dabble-ones 0000 0001 0000 10000000 0000 0010 0001 00000000 0000 0100 0010 00000000 > (double-dabble 220) 0000 0000 0000 11011100 0000 0000 0001 10111000 0000 0000 0011 01110000 0000 0000 0110 11100000 dabble-ones 0000 0001 0011 11000000 0000 0010 0111 10000000 dabble-ones 0000 0101 0101 00000000 dabble-ones dabble-tens 0001 0001 0000 00000000 0010 0010 0000 00000000 > (double-dabble 243) 0000 0000 0000 11110011 0000 0000 0001 11100110 0000 0000 0011 11001100 0000 0000 0111 10011000 dabble-ones 0000 0001 0101 00110000 dabble-ones 0000 0011 0000 01100000 0000 0110 0000 11000000 dabble-tens 0001 0010 0001 10000000 0010 0100 0011 00000000
You can run the program at https://ideone.com/38C0G3.
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] """