[A83] Re: Faster Multiplication


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

[A83] Re: Faster Multiplication




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





Follow-Ups: