Date   : Wed, 15 Jun 2005 16:27:56 +0100
From   : Richard_Talbot-Watkins@...
Subject: Re: Faster 6502 multiplication

Carlo writes:

> This descends from the fact that a*b is *always* an integer,
> so for the above relationship to hold the right side of the
> equation *must* also be an integer value. From this descends
> that (a+b)^2 - (a-b)^2 is always a multiple of 4.
>
> Please note that the single factors (a+b)^2 and (a-b)^2 are
> *not necessarily* multiple of 4. This implies that your
> algorithm should calculate
>
>           (a+b)^2  -  (a-b)^2
>     ab =  ------------------- , not
>                    4
>
>           (a+b)^2     (a-b)^2
>     ab =  -------  -  -------
>              4           4
>
> (that is more efficient as well :)

Your first method would be more efficient than the second if the CPU was
having to divide the term(s) by 4 itself.

But what I am trying to do is get rid of the division by 4 altogether by
looking up "pre-divided-by-4" values from the table.  Remember, that
(a+b)^2 - (a-b)^2 is an 18-bit result, and so would require more byte
lookups and/or some additional bit-shifting to get the result.  I am trying
to create code which is lean on CPU cycles here!

What seems curious to me is that these pre-divided-by-4 values don't seem
to "miss" their discarded two bits at all.

For example, imagine we do not pre-divide the table values by 4, and we get
the following values out, and subtract:

   100000
 -  10011
     1101

Now dividing by 4 (truncating the bottom two bits of the result), we get
the result 11.

This time, we will use pre-divided values (truncating the bottom two bits
of the table values):

   1000(00 truncated)
 -  100(11 truncated)
    100

This yields a result which is one out.  The discrepancy resulted from the
fact that, in the first calculation, there was a borrow from bit 2 when
calculating bit 1 of the result.  In the second calculation, since the
bottom 2 bits are immediately discarded, this didn't happen.

However, this does not appear to EVER happen with the pairs of values
pulled out from the table!  I can only explain it as due to the mystical
voodoo power of square numbers, but I'm sure there's a more mathematical
explanation ;-)

[Alternatively, can someone find a case which breaks my routine?  I used
the not-particularly-exhaustive test of multiplying random numbers and
checking the result with 'reality' until I got bored with waiting...]

Rich


**********************************************************************
This email and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom they
are addressed. If you have received this email in error please notify
postmaster@...

This footnote also confirms that this email message has been checked
for all known viruses.

**********************************************************************
Sony Computer Entertainment Europe