Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
In computing and electronic systems, binary-coded decimal is a digital encoding method for numbers using decimal notation, with each decimal digit represented by its own binary sequence. In BCD, a numeral is usually represented by four bits which, in general, represent the decimal range 0 through 9...
, or BCD, notation). The algorithm operates as follows:
Suppose the original number to be converted is stored in a register
Processor register
In computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...
that is n bits wide. Reserve a scratch space wide enough to hold both the original number and its BCD representation – 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 24310 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 24310, 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.
Another example for the double dabble algorithm - value 6524410.
104 103 102 101 100 ORIGINAL BINARY
0000 0000 0000 0000 0000 1111111011011100 Initialization
0000 0000 0000 0000 0001 1111110110111000 Shift left (1st)
0000 0000 0000 0000 0011 1111101101110000 Shift left (2nd)
0000 0000 0000 0000 0111 1111011011100000 Shift left (3rd)
0000 0000 0000 0000 1010 1111011011100000 Add 3 to 100, since it was 7
0000 0000 0000 0001 0101 1110110111000000 Shift left (4th)
0000 0000 0000 0001 1000 1110110111000000 Add 3 to 100, since it was 5
0000 0000 0000 0011 0001 1101101110000000 Shift left (5th)
0000 0000 0000 0110 0011 1011011100000000 Shift left (6th)
0000 0000 0000 1001 0011 1011011100000000 Add 3 to 101, since it was 6
0000 0000 0001 0010 0111 0110111000000000 Shift left (7th)
0000 0000 0001 0010 1010 0110111000000000 Add 3 to 100, since it was 7
0000 0000 0010 0101 0100 1101110000000000 Shift left (8th)
0000 0000 0010 1000 0100 1101110000000000 Add 3 to 101, since it was 5
0000 0000 0101 0000 1001 1011100000000000 Shift left (9th)
0000 0000 1000 0000 1001 1011100000000000 Add 3 to 102, since it was 5
0000 0000 1000 0000 1100 1011100000000000 Add 3 to 100, since it was 9
0000 0001 0000 0001 1001 0111000000000000 Shift left (10th)
0000 0001 0000 0001 1100 0111000000000000 Add 3 to 100, since it was 9
0000 0010 0000 0011 1000 1110000000000000 Shift left (11th)
0000 0010 0000 0011 1011 1110000000000000 Add 3 to 100, since it was 8
0000 0100 0000 0111 0111 1100000000000000 Shift left (12th)
0000 0100 0000 1010 0111 1100000000000000 Add 3 to 101, since it was 7
0000 0100 0000 1010 1010 1100000000000000 Add 3 to 100, since it was 7
0000 1000 0001 0101 0101 1000000000000000 Shift left (13th)
0000 1011 0001 0101 0101 1000000000000000 Add 3 to 103, since it was 8
0000 1011 0001 1000 0101 1000000000000000 Add 3 to 101, since it was 5
0000 1011 0001 1000 1000 1000000000000000 Add 3 to 100, since it was 5
0001 0110 0011 0001 0001 0000000000000000 Shift left (14th)
0001 1001 0011 0001 0001 0000000000000000 Add 3 to 103, since it was 6
0011 0010 0110 0010 0010 0000000000000000 Shift left (15th)
0011 0010 1001 0010 0010 0000000000000000 Add 3 to 102, since it was 6
0110 0101 0010 0100 0100 0000000000000000 Shift left (16th)
6 5 2 4 4
BCD
Sixteen shifts have been performed, so the algorithm terminates. The BCD digits is: 6*104 + 5*103 + 2*102 + 4*101 + 4*100 = 65244.
C implementation
The double dabble algorithm might look like this when implemented in C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
. 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
Malloc
C dynamic memory allocation refers to performing dynamic memory allocation in the C via a group of functions in the C standard library, namely malloc, realloc, calloc and free....
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
include
include
/*
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;
}
VHDL Implementation
The double dabble algorithm can be implemented as a VHDL function.The VHDL code can be accessed here.The code converts 8 bit binary value into 12 bit BCD data(containing 3 BCD digits).
Historical
In the 1960s, the term double dabble was also used for the mental algorithm used by programmers to convert a binary number to decimal. It is performed by reading the binary number from left to right, doubling if the next bit is zero, and doubling and adding one if the next bit is one. In the example above, 11110011, the thought process would be: "one, three, seven, fifteen, thirty, sixty, one hundred twenty-one, two hundred forty-three," the same result as that obtained above.
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
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: