Binary Coded Decimal Arithmetic

One thing we haven't addressed at all is the relative difficulty of doing arithmetic vs. reading and writing numbers. Suppose we take a typical application: a calculator. The user presses keypad buttons to enter a number; we display the number. When an arithmetic operation is requested we perform the operation, and then display the result.

So, it looks like when they type in the number the calculator has to keep multiplying the number it was previously storing by 10, and then adding in our new digit, to get the new number. When we press the ``+'' key the calculator performs the addition; then it does a binary-to-decimal conversion to display the result.

Hey, wait a minute -- look at the ratio of ``calculation work'' to ``IO work'' here! Especially when you consider that multiplications are 10 cycles, and divisions are 41 cycles, each.

Not to mention our calculator can only hold a number up to 65536 (and, since the MUL instruction takes two eight bit operands, even getting up that high would take a lot of finessing. There's a well-known divide-and-conquer algorithm for multiplication like this; see http://www.cs.nmsu.edu/~pfeiffer/classes/273/notes/multiply2.html). Something is wrong here.... maybe we can use a different representation that will cut down on the amount of work we have to do in the IO part (though increasing the work in the calculation part) enough to reduce the total amount of work required. If we do it right, we can get a useful size number to fit, too.

The representation we will use is called ``binary coded decimal.'' The idea is, instead of representing a number in binary, we'll represent it as an array of decimal digits. Now, to add, we can just do the following for every digit of x and y.

  1. Load x digit into accumulator
  2. Add y digit to it
  3. If result is greater than 10,
    1. Subtract 10 from result
    2. Make sure to add a carry into the next place over
  4. Store result
We've just made addition much more painful, but displaying a result is much, much easier and we can make the array as wide as we want. But maybe we can do better yet: notice that we never use half the bits in each place. Maybe we can pack two digits into every array element? Yes, we can.

Packed BCD

OK, that's what we'll do. If we're clever, maybe we can even make it easier to do arithmetic at the same time. Let's ask what happens if we add two packed BCD numbers together... we have three cases involving the least significant nybble:

  1. Case 1: the result is less than 10. The addition is correct.

  2. Case 2: the least significant nybble gets a result greater than 9 but less than 16. We need to subtract 10 from the least significant nybble, and add 1 to the most significant nybble.

  3. Case 3: the least significant nybble gets a result greater than 15. We need to subtract 10 from the least significant nybble (we don't need to add 1 to the most significant nybble, because we already had a carry into those bits). Note that we can't use the four bits themselves to see if we've got this case; the values in the bits aren't distinguishable from getting a 1 (for 17), 2 (for 18), or 3 (for 19) which would be the same as the first case. So, we need an extra condition code bit to keep track of whether there is a carry across the nybbles - precisely the purpose of the H bit.

There are three corresponding cases for the most significant nybble.

This, of course, looks like a mess to try to implement. Unless we have an instruction in the instruction set to do it for us - like the DAA (Decimal Adjust A) instruction! This instruction applies exactly the adjustments we described above.

Now we can add two packed BCD strings of arbitrary length (limited by memory size, of course). The central loop looks like 


loop    ldaa    op1,x
        adca    op2,x
        daa
        staa    res,x
        dex
        bne     loop

(notice, by the way, that this same basic loop but missing the daa instruction would let us do arbitrary precision arithmetic.

We subtract by using 10's complement. Mom's Comptometer strikes again!

As a last aside, I don't really know whether real calculators as sold today use a BCD representation or a pure binary representation internally. The program language COBOL, which is intended for business applications, does have built-in datatype for BCD numbers, though.

Last modified: Fri Nov 11 12:50:58 MST 2005