Double dabble

Key takeaways

Double dabble belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Double dabble to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Double dabble from memory before moving on to harder problems.

Reference excerpt

In computer science, the double dabble algorithm is used to convert binary numbers into binary-coded decimal (BCD) notation. 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.

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×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 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

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 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 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 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 decimal value of the BCD digits is: 6*104 + 5*103 + 2*102 + 4*101 + 4*100 = 65244.

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:

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 ========================== 24310

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Double dabble

Start with the simplest possible case. Write down what Double dabble claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Double dabble before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Double dabble ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Double dabble

In research: Double dabble appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Double dabble in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Double dabble is common in secondary-school and first-year university syllabi. It links to neighbouring topics Binary arithmetic, Shift-and-add algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Double dabble outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Double dabble in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Double dabble means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Double dabble out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Double dabble in simple terms?

In computer science, the double dabble algorithm is used to convert binary numbers into binary-coded decimal (BCD) notation. 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.

Why does Double dabble matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Double dabble?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Double dabble.