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 <allomber@math.u-bordeaux.fr> 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 sometimes. Cheers, Bill.