Re: A86: a pretty fast multiply method...


[Prev][Next][Index][Thread]

Re: A86: a pretty fast multiply method...




Kirk Meyer wrote:
> After trying and trying, I have found a really fast way to multiply two
> 8-bit numbers and get a 16-bit result. The problem is we want to find A * B.
> 
> Well it just so happens that A * B = (A+B)(A+B)/4 - (A-B)(A-B)/4
> If you inspect this for a minute, you'll see something really cool... in
> order to do multiplication all we need is a table of squares (actually a
> table of squares divided by four) and two lookups into the table.

Steve Judd of Commodore 64 fame figured this out a few years ago, and
implemented some pretty darn fast and cool routines - very decent frame
rates, and this is at 1Mhz with a 320x200 pixel screen!

This is from him:
"Fast multiply: don't blink or you'll miss it.

Let f(x) = x^2 / 4.  Then

                a*b = f(a+b) - f(a-b)

Thus with a table of squares you can do integer multiplies very quickly.
To see an implementation of this algorithm, see C=Hacking."

6502 source and binaries:
http://www.ffd2.com/fridge/obj3d/index.html

For a couple absolutely huge articles on how he did this:
http://www.ffd2.com/fridge/chacking/c=hacking16.txt
http://www.ffd2.com/fridge/chacking/c=hacking18.txt

And while I'm at it, a bunch of great Spectrum vs. C64 vs. Z80 vs. 6502 flamewars:
http://www.ffd2.com/fridge/speccy/
--
Robin Harbron     macbeth@psw.nu
 http://www.tbaytel.net/macbeth
       http://www.psw.nu/


Follow-Ups: References: