Re: [stella] optimization : sneaky fractional bit representation

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