Note: this page formats the tables using <code> and <pre>. To display properly, you have to be using a monospace font for code samples. I think that's pretty standard, but if the formatting doesn't make sense you'll want to check.
How to multiply? As usual, doing it in binary is just like decimal, only easier. We'll show it with a four-bit word; wider words are just the same, but take more space to show the example. This page will start by showing the standard pencil-and-paper multiplication algorithm, and gently transmogrify it into something more suitable for a computer implementation.
0101 1011 ------ 0101 0101 0000 0101 -------- 00110111
Of course, we can re-order the operations a bit and compute partial results as we go:
00000000 0101 1 -------- 00000101 0101 1 -------- 00001111 0000 0 -------- 00001111 0101 1 -------- 00110111
Can we make a table like we did for number base conversions? Let's try.
old bit add new 00000000 1 00000101 00000101 00000101 1 00001010 00001111 00001111 0 00000000 00001111 00001111 1 01010000 00110111
Let's underline the bits we're concerned with in each step. Because we're going to end up being a bit tricky with the multiplier later, we're going to show the entire multiplier with the important bit on every step underlined, instead of just the relevant bit like we did in the last step.
old mplier add new 00000000 1011 00000101 00000101 00000101 1011 00001010 00001111 00001111 1011 00000000 00001111 00001111 1011 00101000 00110111
Now let's just put the tables on a slant, so the bits we're interested in are vertically aligned.
old mplier add new 00000000 1011 00000101 00000101 00000101 1011 00001010 00001111 00001111 1011 00000000 00001111 00001111 1011 00101000 00110111
Now we can crop a little bit: we won't show the bits for the "old" column that haven't been created yet, we won't show the bits for the "mplier" column that have been retired, and we won't show the "add" column at all.
old mplier new 0000 1011 00101 00101 101 001111 001111 10 0001111 0001111 1 00110111
So now it looks more like we're moving the data through the algorithm... The interesting thing here is that at every step we're only doing a four-bit add, based on the contents of a single other bit! Also, that we can do all our work with a single double-wide register: initially the right half contains the multiplier, while the left half is empty. On each iteration, we use the least-significant bit of the multiplier to decide whether or not to add; we can add into the left side. Then we can shift the whole thing one bit to the right, disposing of the bit we just used in the decision, and shifting the carry-out from the add in the left.
At this point, what we've got looks a lot like the following algorithm:
Assume a double-width register. Put the multiplier in the least significant half, and clear the most significant half.
If there are n bits in a single-width register, perform the following n times:
If the least significant bit of the register contains a 1, add the multiplicand to the most significant half.
Shift the whole register one bit to the right, throwing away the least significant bit and shifting the carry bit into the most significant bit.
Can we do this in the A and B accumulators? Yes. We need to
introduce some shift instructions to do it, in particular the
asra and asrb instructions.
Assume we want to multiply a number in a memory location called mplier by one in a location called mcand.
ldab mplier * b contains multiplier clra * a is initially 0 ldx #8 * this will take 8 passes loop clc * we want to make sure that if we don't add, the * carry bit contains a 0 to shift in. bitb #%00000001 * check lsb of m'plier beq noadd * if it's a 1... adda mcand * ...do an add noadd rora * shift result one bit to the right (and shift carry in) rorb * throw away m'plier bit we just used and look at next one dex bne loop
Nearly all computers actually have a multiply instruction - including
the HC11. On this machine, we can perform an 8x8 multiply, giving a
16 bit result, by putting the two operands in the A and B accumulators
and using a MUL. The 16 bit result is in the D
accumulator.