Bill Allombert on Tue, 13 Jan 2004 00:35:05 +0100

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

Re: some PARI kernel oddities/remarks

On Mon, Jan 12, 2004 at 03:13:09PM -0800, Phil Carmody wrote:
> --- Bill Allombert <> wrote:
> > 4) In the (a+b)^2-a^2-b^2=2*a*b formula, we can detect high word
> > cancellation when a and are of different length (which can happen).
> > Is it wortwhile to implement it for t_INT ? for Flx ?
> Was ((a+b)^2-(a-b)^2)>>1 considered?
> If 3 squares is fast, then 2 should be faster, surely?

In the context of Karatsuba multiplication you already have 
computed a^2 and b^2. In fact the trick lead to 1 squaring 
and 3 add/sub instead of a multiplication and a shift.

A shift cost rougly the same as a add.
Using high word cancellation, we can make the add/sub a bit faster