Double dabble

From Wikipedia, the free encyclopedia

In computer science, the double dabble algorithm is used to convert binary numbers into decimal (in particular, binary-coded decimal, or BCD, notation). The algorithm operates as follows:

Suppose the original number to be converted is stored in a register that is n bits wide. Reserve a scratch space wide enough to hold both the original number and its BCD representation — $n + 4 n / 3$ bits will be enough. Partition the scratch space into BCD digits (on the left) and the original register (on the right). For example, if the original number to be converted is eight bits wide, the scratch space would be partitioned as follows:

100S TENS ONES ORIGINAL
0010 0100 0011 11110011

The diagram above shows the binary representation of 243₁₀ in the original register, and the BCD representation of 243 on the left.

The scratch space is initialized to all zeros, and then the value to be converted is copied into the "original register" space on the right.

0000 0000 0000 11110011

Then, the algorithm iterates n times. On each iteration, the entire scratch space is left-shifted one bit. However, before the left-shift is done, any BCD digit which is greater than 4 is incremented by 3. The increment ensures that a value of 5, incremented and left-shifted, becomes 16, thus correctly "carrying" into the next BCD digit.

The double-dabble algorithm, performed on the value 243₁₀, looks like this:

0000 0000 0000 11110011      Initialization
0000 0000 0001 11100110      Shift
0000 0000 0011 11001100      Shift
0000 0000 0111 10011000      Shift
0000 0000 1010 10011000      Add 3 to ONES, since it was 7
0000 0001 0101 00110000      Shift
0000 0001 1000 00110000      Add 3 to ONES, since it was 5
0000 0011 0000 01100000      Shift
0000 0110 0000 11000000      Shift
0000 1001 0000 11000000      Add 3 to TENS, since it was 6
0001 0010 0001 10000000      Shift
0010 0100 0011 00000000      Shift

Now eight shifts have been performed, so the algorithm terminates. The BCD digits to the left of the "original register" space display the BCD encoding of the original value 243.

[edit] C implementation

The double dabble algorithm might look like this when implemented in C. Notice that this implementation is designed to convert an "input register" of any width, by taking an array as its parameter and returning a dynamically allocated string. Also notice that this implementation does not store an explicit copy of the input register in its scratch space, as the description of the algorithm did; copying the input register into the scratch space was just a pedagogical device.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/*
   This function takes an array of n unsigned integers,
   each holding a value in the range [0, 65535],
   representing a number in the range [0, 2**(16n)-1].
   arr[0] is the most significant "digit".
   This function returns a new array containing the given
   number as a string of decimal digits.
 
   For the sake of brevity, this example assumes that
   calloc and realloc will never fail.
*/
void double_dabble(int n, const unsigned int *arr, char **result)
{
    int nbits = 16*n;         /* length of arr in bits */
    int nscratch = nbits/3;   /* length of scratch in bytes */
    char *scratch = calloc(1 + nscratch, sizeof *scratch);
    int i, j, k;
    int smin = nscratch-2;    /* speed optimization */
 
    for (i=0; i < n; ++i) {
        for (j=0; j < 16; ++j) {
            /* This bit will be shifted in on the right. */
            int shifted_in = (arr[i] & (1 << (15-j)))? 1: 0;
 
            /* Add 3 everywhere that scratch[k] >= 5. */
            for (k=smin; k < nscratch; ++k)
              scratch[k] += (scratch[k] >= 5)? 3: 0;
 
            /* Shift scratch to the left by one position. */
            if (scratch[smin] >= 8)
              smin -= 1;
            for (k=smin; k < nscratch-1; ++k) {
                scratch[k] <<= 1;
                scratch[k] &= 0xF;
                scratch[k] |= (scratch[k+1] >= 8);
            }
 
            /* Shift in the new bit from arr. */
            scratch[nscratch-1] <<= 1;
            scratch[nscratch-1] &= 0xF;
            scratch[nscratch-1] |= shifted_in;
        }
    }
 
    /* Remove leading zeros from the scratch space. */
    for (k=0; k < nscratch-1; ++k)
      if (scratch[k] != 0) break;
    nscratch -= k;
    memmove(scratch, scratch+k, nscratch+1);
 
    /* Convert the scratch space from BCD digits to ASCII. */
    for (k=0; k < nscratch; ++k)
      scratch[k] += '0';
 
    /* Resize and return the resulting string. */
    *result = realloc(scratch, nscratch+1);
    return;
}
 
/*
   This test driver should print the following decimal values:
   246
   16170604
   1059756703745
*/
int main(void)
{
    unsigned int arr[] = { 246, 48748, 1 };
    char *text = NULL;
    int i;
    for (i=0; i < 3; ++i) {
        double_dabble(i+1, arr, &text);
        printf("%s\n", text);
        free(text);
    }
    return 0;
}