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.

Advertisements

Pages: 1 2

3 Responses to “Double Dabble”

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

  2. Daniel said

    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:

    $ ./double_dabble 42
    0000 0000 0000 0000 0000 0000 0100 0010
    
    $ ./double_dabble 220
    0000 0000 0000 0000 0000 0010 0010 0000
    
    $ ./double_dabble 243
    0000 0000 0000 0000 0000 0010 0100 0011
    
  3. Paul said

    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]
    """
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: