Re: [stella] optimization : sneaky fractional bit representation

Subject: Re: [stella] optimization : sneaky fractional bit representation
From: Robin Harbron <macbeth@xxxxxxxxxxxxxxxxxxx>
Date: Thu, 04 Jun 1998 07:28:21 -0400
Chris Wilkson wrote:
> 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!

For lots of cool 65xx code, check out The Fridge:
http://stratus.esam.nwu.edu/~judd/fridge/

Under the math section:

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.

I've actually coded this, and yes, it is really fast.
I believe Steve Judd has done an implementation of it in
Commodore Hacking #9 -
http://stratus.esam.nwu.edu/~judd/fridge/chacking/
He's also got another article on 3d graphics in C=Hacking #13.
-- 
Robin Harbron    macbeth@xxxxxxxxxxx
   http://www.tbaytel.net/macbeth


--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/stella.html

Current Thread