Subject: Re: [stella] optimization : sneaky fractional bit representation From: Chris Wilkson <cwilkson@xxxxxxxxxxxxxxxx> Date: Wed, 3 Jun 1998 19:12:25 -0700 (PDT) |
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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [stella] optimization : sneaky , Erik Mooney | Thread | Re: [stella] optimization : sneaky , Robin Harbron |
Re: [stella] optimization : sneaky , Erik Mooney | Date | Re: [stella] optimization : sneaky , Robin Harbron |
Month |