Binary coded decimal

Created 13th August, 2009 04:21 (UTC), last edited 13th August, 2009 04:37 (UTC)

I don't know about you, but these days I take the binary to decimal conversions that my programs do entirely for granted. It wasn't always like that of course. Back in the day when I was learning machine code on a ZX Spectrum converting binary to decimal was long winded and complex. Long winded and complex meant that it took a lot of instructions which meant that all the time you were trying to display the player's score you weren't moving the game along. There had to be a better way.

The way that the Zilog Z80 solved the problem was to have a special arithmetic mode with some odd properties. Basically the result of adding one to nine was 16 and the result of subtracting one from 256 was 153. If that doesn't make much sense then convert the numbers to hex. 0x9 + 0x1 gives 0x10 and 0x100 minus 0x1 gives 0x99.

Binary coded decimal works by taking the hex representation of a number and then interpreting that as a decimal number without further conversion. The hex digits of 0xa through 0xf were simply disallowed. The decimal number 66 written in hex is 0x42, so in binary coded decimal it represents the number 42 instead, and the decimal number 1337 in binary coded decimal is 4919 (0x1337).

The big advantage of this mechanism was that you could get a single digit to display by masking off the relevant nibble (possibly with a shift) and then adding that value to the character code for zero. The Z80 had some special instructions that made adding and subtracting binary coded decimal easy. That's where the puzzle comes in.

Write add and subtract functions that takes two binary coded decimal numbers where each is an array/list/tuple of bytes. Also write a function for displaying these numbers.

It doesn't matter if the first element of your structure is the least or the most significant pair of digits, but you must store two digits per byte (or cell if your language just has numbers). Your code should work for binary coded decimal values of arbitrary length.

You can check that your code works as expected by writing a Fibonacci number generator that uses the addition function. If you want to try something a (little) bit harder then write a multiply function and use that to write a factorial implementation.