Ack! You beat me to it! :) I'll have to look at your post later, Erik.
The obvious is a lookup table. But that would be one *HUGE* lookup table.
But here are a couple of reasonable ways of doing it.
I have to be leaving pretty soon. So even though it may be repeating what
you've already said, here's a compact routine to multiply 2 4-bit numbers
that are stored in zero-page. The result is left in the accumulator.
This can be extended by using the carry bit between bytes.
; foo1 and foo2 are the addresses of the two numbers
; accumulator must equal zero
; the routine starts at the "mul" label
loop asl foo2 ; muliply by 2
mul lsr foo1 ; divide by 2 ; this is the entry point
bcc zero ; did we lose a one? if not, do nothing
clc ; if so add foo2 to the total
adc foo2 ; add the current value of foo2
zero bne loop ; stop if foo1 is zero or if foo2 started as zero
Looking at your description, I think this may be the short (bit wise) form
of your alogorithm. I'll figure it out tonight when I have more time... :)
In the meantime, here's a way to use a compressed lookup table.
I don't have time to try to code this thing, and I don't remember it off
the top of my head. I'll try to code it tonight. But the idea is to create
a table of squares and use the algebra below.
a*b...
(a+b)^2 = (a+b)(a+b) = a^2 + 2ab + b^2 ; binomial expansion
2ab = (a+b)^2 - a^2 - b^2
ab = [(a+b)^2 - a^2 - b^2] / 2
Now you can do 3 indexed lookups, 2 subractions, and a shift to multiply
any two numbers together!
-Chris
> Wonder of wonders, we *just* went over an algorithm for that 30 minutes ago
> in my computers class. To multiply C by B, where both are eight digit
> registers, you need one extra 8-bit storage area (we'll call it A) and one
> 1-bit storage area (we'll call it E.). C gets destroyed, but B remains
> intact. Initialize C and E to 0.
> Repeat 8 times:
> If bit 0 of C is 1, then add B to C, carrying into E if necessary.
> Shift the 17-bit quantity EAC to the right.
>
> This puts the product as a 16-bit quantity in AC.
--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/stella.html
