[A83] Re: Faster Multiplication


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

[A83] Re: Faster Multiplication




On Wed, 30 May 2001 17:46:31 -0600, assembly-83@lists.ticalc.org
wrote:
>If you're looking to multiply things quickly: Instead of using a
>less than
>optimal bit shift algorithm (which you haven't even unrolled), maybe
>you
>ought to look into this algorithm. Requires either 1kb or 1.5kb of
>tables
>(generated at runtime), depending on how you implement it. The
>resulting Z80
>code is ~100 constant tstates per multiply. Now thats fast.
>
> (x+y)^2-(x-y)^2 = 4xy
>
>Or:
>
> x*y = ((x+y)^2)/4-((x-y)^2)/4
>
>Thus you can find the product of any two numbers through the
>difference of
>two squares, and therefore all you need is a table of 511 squares
>(values 0
>to 255+255=510). Note that mathemtically the remainders of the /4
>will
>cancel out in the subtraction, so all that needs to be stored in a
>table is
>the square divided by 4, which is fortunate since 512^2 would
>otherwise
>overflow a word.
>
>Example: (3+8)^2-(3-8)^2 = 4(3*8)
>        121 - 25 = 4 * xy
>        xy = 96/4 = 24
>

What is an algorithm? How about a table? How can you use an equation
like that in assembly? Sorry about the trivial questions...I'm
learning. Thanks!
-Tom Lutz
caffeine43@netzero.net on 05/30/2001




Follow-Ups: References: