Double dabble

Last updated March 08, 2024

In computer science, the double dabble algorithm is used to convert binary numbers into binary-coded decimal (BCD) notation.^[1]^[2] It is also known as the shift-and-add-3 algorithm, and can be implemented using a small number of gates in computer hardware, but at the expense of high latency.^[3]

Algorithm

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\times ceil (n /3)$ bits will be enough. It takes a maximum of 4 bits in binary to store each decimal digit.

Then 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:

Hundreds 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

The algorithm then iterates n times. On each iteration, any BCD digit which is at least 5 (0101 in binary) is incremented by 3 (0011); then the entire scratch space is left-shifted one bit. The increment ensures that a value of 5, incremented and left-shifted, becomes 16 (10000), thus correctly "carrying" into the next BCD digit.

Essentially, the algorithm operates by doubling the BCD value on the left each iteration and adding either one or zero according to the original bit pattern. Shifting left accomplishes both tasks simultaneously. If any digit is five or above, three is added to ensure the value "carries" in base 10.

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    2    4    3        BCD

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 65244₁₀.

 10⁴  10³  10²   10¹  10⁰    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 10⁰, since it was 7 0000 0000 0000 0001 0101   1110110111000000   Shift left (4th) 0000 0000 0000 0001 1000   1110110111000000   Add 3 to 10⁰, 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 10¹, since it was 6 0000 0000 0001 0010 0111   0110111000000000   Shift left (7th) 0000 0000 0001 0010 1010   0110111000000000   Add 3 to 10⁰, since it was 7 0000 0000 0010 0101 0100   1101110000000000   Shift left (8th) 0000 0000 0010 1000 0100   1101110000000000   Add 3 to 10¹, since it was 5 0000 0000 0101 0000 1001   1011100000000000   Shift left (9th) 0000 0000 1000 0000 1001   1011100000000000   Add 3 to 10², since it was 5 0000 0000 1000 0000 1100   1011100000000000   Add 3 to 10⁰, since it was 9 0000 0001 0000 0001 1001   0111000000000000   Shift left (10th) 0000 0001 0000 0001 1100   0111000000000000   Add 3 to 10⁰, since it was 9 0000 0010 0000 0011 1000   1110000000000000   Shift left (11th) 0000 0010 0000 0011 1011   1110000000000000   Add 3 to 10⁰, since it was 8 0000 0100 0000 0111 0111   1100000000000000   Shift left (12th) 0000 0100 0000 1010 0111   1100000000000000   Add 3 to 10¹, since it was 7 0000 0100 0000 1010 1010   1100000000000000   Add 3 to 10⁰, since it was 7 0000 1000 0001 0101 0101   1000000000000000   Shift left (13th) 0000 1011 0001 0101 0101   1000000000000000   Add 3 to 10³, since it was 8 0000 1011 0001 1000 0101   1000000000000000   Add 3 to 10¹, since it was 5 0000 1011 0001 1000 1000   1000000000000000   Add 3 to 10⁰, since it was 5 0001 0110 0011 0001 0001   0000000000000000   Shift left (14th) 0001 1001 0011 0001 0001   0000000000000000   Add 3 to 10³, since it was 6 0011 0010 0110 0010 0010   0000000000000000   Shift left (15th) 0011 0010 1001 0010 0010   0000000000000000   Add 3 to 10², 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 decimal value of the BCD digits is: 6*10⁴ + 5*10³ + 2*10² + 4*10¹ + 4*10⁰ = 65244.

Parametric Verilog implementation

// parametric Verilog implementation of the double dabble binary to BCD converter// for the complete project, see// https://github.com/AmeerAbdelhadi/Binary-to-BCD-Convertermodulebin2bcd#(parameterW=18)// input width(input[W-1:0]bin,// binaryoutputreg[W+(W-4)/3:0]bcd);// bcd {...,thousands,hundreds,tens,ones}integeri,j;always@(bin)beginfor(i=0;i<=W+(W-4)/3;i=i+1)bcd[i]=0;// initialize with zerosbcd[W-1:0]=bin;// initialize with input vectorfor(i=0;i<=W-4;i=i+1)// iterate on structure depthfor(j=0;j<=i/3;j=j+1)// iterate on structure widthif(bcd[W-i+4*j-:4]>4)// if > 4bcd[W-i+4*j-:4]=bcd[W-i+4*j-:4]+4'd3;// add 3endendmodule

^[4]

Parametric Verilog implementation of the double dabble binary to BCD converter, 18-bit example. Bin2BCD-DoubleDabble2.svg — Parametric Verilog implementation of the double dabble binary to BCD converter, 18-bit example.

Reverse double dabble

The algorithm is fully reversible. By applying the reverse double dabble algorithm a BCD number can be converted to binary. Reversing the algorithm is done by reversing the principal steps of the algorithm:

The principal steps of the algorithms
Double dabble (Binary to BCD)	Reverse double dabble (BCD to binary)
For each group of input four bits: If group >= 5 add 3 to group Left shift into the output digits	Right shift into the output binary For each group of four input bits: If group >= 8 subtract 3 from group

Reverse double dabble example

The reverse double dabble algorithm, performed on the three BCD digits 2-4-3, looks like this:

    BCD Input      Binary                     Output    2    4    3  0010 0100 0011   00000000   Initialization  0001 0010 0001   10000000   Shifted right  0000 1001 0000   11000000   Shifted right  0000 0110 0000   11000000   Subtracted 3 from 2nd group, because it was 9  0000 0011 0000   01100000   Shifted right  0000 0001 1000   00110000   Shifted right  0000 0001 0101   00110000   Subtracted 3 from 3rd group, because it was 8  0000 0000 1010   10011000   Shifted right  0000 0000 0111   10011000   Subtracted 3 from 3rd group, because it was 10  0000 0000 0011   11001100   Shifted right  0000 0000 0001   11100110   Shifted right  0000 0000 0000   11110011   Shifted right ==========================                        243₁₀

Historical

In the 1960s, the term double dabble was also used for a different 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.^[5] 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.

Related Research Articles

In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each digit is represented by a fixed number of bits, usually four or eight. Sometimes, special bit patterns are used for a sign or other indications.

Golden ratio base is a non-integer positional numeral system that uses the golden ratio as its base. It is sometimes referred to as base-φ, golden mean base, phi-base, or, colloquially, phinary. Any non-negative real number can be represented as a base-φ numeral using only the digits 0 and 1, and avoiding the digit sequence "11" – this is called a standard form. A base-φ numeral that includes the digit sequence "11" can always be rewritten in standard form, using the algebraic properties of the base φ — most notably that φ¹ + φ⁰ = φ². For instance, 11_φ = 100_φ.

A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one).

In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operations and directly supported by the processor. Most bitwise operations are presented as two-operand instructions where the result replaces one of the input operands.

Two's complement is the most common method of representing signed integers on computers, and more generally, fixed point binary values. Two's complement uses the binary digit with the greatest place value as the sign to indicate whether the binary number is positive or negative. When the most significant bit is 1, the number is signed as negative; and when the most significant bit is 0 the number is signed as positive.

In mathematics and computing, the method of complements is a technique to encode a symmetric range of positive and negative integers in a way that they can use the same algorithm for addition throughout the whole range. For a given number of places half of the possible representations of numbers encode the positive numbers, the other half represents their respective additive inverses. The pairs of mutually additive inverse numbers are called complements. Thus subtraction of any number is implemented by adding its complement. Changing the sign of any number is encoded by generating its complement, which can be done by a very simple and efficient algorithm. This method was commonly used in mechanical calculators and is still used in modern computers. The generalized concept of the radix complement is also valuable in number theory, such as in Midy's theorem.

Excess-3, 3-excess or 10-excess-3 binary code, shifted binary or Stibitz code is a self-complementary binary-coded decimal (BCD) code and numeral system. It is a biased representation. Excess-3 code was used on some older computers as well as in cash registers and hand-held portable electronic calculators of the 1970s, among other uses.

PiHex was a distributed computing project organized by Colin Percival to calculate specific bits of $π$ . 1,246 contributors used idle time slices on almost two thousand computers to make its calculations. The software used for the project made use of Bellard's formula, a faster version of the BBP formula.

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth's algorithm is of interest in the study of computer architecture.

Reed–Muller codes are error-correcting codes that are used in wireless communications applications, particularly in deep-space communication. Moreover, the proposed 5G standard relies on the closely related polar codes for error correction in the control channel. Due to their favorable theoretical and mathematical properties, Reed–Muller codes have also been extensively studied in theoretical computer science.

ISO 8583 is an international standard for financial transaction card originated interchange messaging. It is the International Organization for Standardization standard for systems that exchange electronic transactions initiated by cardholders using payment cards.

ThaiURL is a technology enabling the use of Thai domain names in applications that have been modified to support this technology. It is one of several such systems that were marketed before the advent of IDNA.

In computer science, a scale factor is a number used as a multiplier to represent a number on a different scale, functioning similarly to an exponent in mathematics. A scale factor is used when a real-world set of numbers needs to be represented on a different scale in order to fit a specific number format. Although using a scale factor extends the range of representable values, it also decreases the precision, resulting in rounding error for certain calculations.

A carry-save adder is a type of digital adder, used to efficiently compute the sum of three or more binary numbers. It differs from other digital adders in that it outputs two numbers, and the answer of the original summation can be achieved by adding these outputs together. A carry save adder is typically used in a binary multiplier, since a binary multiplier involves addition of more than two binary numbers after multiplication. A big adder implemented using this technique will usually be much faster than conventional addition of those numbers.

<span class="mw-page-title-main">Fast inverse square root</span> Root-finding algorithm

Fast inverse square root, sometimes referred to as Fast InvSqrt or by the hexadecimal constant 0x5F3759DF, is an algorithm that estimates $, the reciprocal of the square root of a 32-bit floating-point number in IEEE 754 floating-point format. The algorithm is best known for its implementation in 1999 in Quake III Arena, a first-person shooter video game heavily based on 3D graphics. With subsequent hardware advancements, especially the x86 SSE instruction rsqrtss, this algorithm is not generally the best choice for modern computers, though it remains an interesting historical example.$

Single-precision floating-point format is a computer number format, usually occupying 32 bits in computer memory; it represents a wide dynamic range of numeric values by using a floating radix point.

The ones' complement of a binary number is the value obtained by inverting (flipping) all the bits in the binary representation of the number. The name "ones' complement" refers to the fact that such an inverted value, if added to the original, would always produce an "all ones" number. This mathematical operation is primarily of interest in computer science, where it has varying effects depending on how a specific computer represents numbers.

A half-carry flag is a condition flag bit in the status register of many CPU families, such as the Intel 8080, Zilog Z80, the x86, and the Atmel AVR series, among others. It indicates when a carry or borrow has been generated out of the least significant four bits of the accumulator register following the execution of an arithmetic instruction. It is primarily used in decimal (BCD) arithmetic instructions.

<span class="mw-page-title-main">Bit-paired keyboard</span>

A bit-paired keyboard is a keyboard where the layout of shifted keys corresponds to columns in the ASCII (1963) table, archetypally the Teletype Model 33 (1963) keyboard. This was later contrasted with a typewriter-paired keyboard, where the layout of shifted keys corresponds to electric typewriter layouts, notably the IBM Selectric (1961). The difference is most visible in the digits row : compared with mechanical typewriters, bit-paired keyboards remove the _ character from 6 and shift the remaining &* from 7890 to 6789, while typewriter-paired keyboards replace 3 characters: ⇧ Shift+2 from " to @⇧ Shift+6 from _ to ^ and ⇧ Shift+8 from ' to *. An important subtlety is that ASCII was based on mechanical typewriters, but electric typewriters became popular during the same period that ASCII was adopted, and made their own changes to layout. Thus differences between bit-paired and (electric) typewriter-paired keyboards are due to the differences of both of these from earlier mechanical typewriters.

Snowflake IDs, or snowflakes, are a form of unique identifier used in distributed computing. The format was created by X and is used for the IDs of tweets. It is popularly believed that every snowflake has a unique structure, so they took the name "snowflake ID". The format has been adopted by other companies, including Discord and Instagram. The Mastodon social network uses a modified version.

References

↑ Gao, Shuli; Al-Khalili, D.; Chabini, N. (June 2012), "An improved BCD adder using 6-LUT FPGAs", IEEE 10th International New Circuits and Systems Conference (NEWCAS 2012), pp. 13–16, doi:10.1109/NEWCAS.2012.6328944, S2CID 36909518
↑ "Binary-to-BCD Converter: "Double-Dabble Binary-to-BCD Conversion Algorithm"" (PDF). Archived from the original (PDF) on 2012-01-31.
↑ Véstias, Mario P.; Neto, Horatio C. (March 2010), "Parallel decimal multipliers using binary multipliers", VI Southern Programmable Logic Conference (SPL 2010), pp. 73–78, doi:10.1109/SPL.2010.5483001, S2CID 28360570
1 2 Abdelhadi, Ameer (2019-07-07), AmeerAbdelhadi/Binary-to-BCD-Converter , retrieved 2020-03-03
↑ Godse, Deepali A.; Godse, Atul P. (2008). Digital Techniques. Pune, India: Technical Publications. p. 4. ISBN 978-8-18431401-4.