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!
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.
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.