So, how do we multiply if we want operands greater than 8 bits and a result greater than 16 bits? Obviously, we could just extend the techniques from the multiplication algorithm, but we'd rather find a way to leverage the multiply instruction.
To do this, we'll observe that we can consider a byte to be a digit in radix 256. It meets the requirements: it can take a value from 0 to 255, and in a multi-byte value each byte is multiplied by 256i where i is which byte you're looking at.
If we think in these terms, we can think of a 24x24 multiplication
(giving a 48 bit result) as multiplying two 3-digit values together,
and we can consider the MUL instruction as performing a
one-digit multiply. If we do that, our picture of our multiplication
looks like this:
Now we can take each of the three multiplies apart, giving us
So, now, to actually perform the multiplication:
So... here's a link to the code, as modified in class on 4/26/04. The question is: is the carry propagation actually fixed?