Date   : Wed, 15 Jun 2005 16:52:27 +0200
From   : Carlo <radiorama@...>
Subject: Re: Faster 6502 multiplication

Richard_Talbot-Watkins@... wrote:

> There is a method which yields the product of two values from the
> difference between two squares.

<snip>

>         (a+b)^2     (a-b)^2
>   ab =  -------  -  -------
>            4           4

<snip>

> Curiously, the integer division by 4 - and hence, truncation of the values
> stored in the tables - doesn't appear to sacrifice any accuracy.  It's as
> if there's never any 'borrow' from bit 2 to bit 1 in any of the
> subtractions it ever performs, but I haven't investigated *why* this should
> be.  Perhaps someone else can explain?

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 :)

Ciao,
Carlo.