ToomN2 with "factored" evaluation

Niels Möller nisse at
Wed Nov 18 11:45:21 CET 2009

Alberto Zanoni <zanoni at> writes:

> I pointed out some time ago that in this case there is one benefit to exploit: 
> one can evaluate b in the needed points just once (instead of about 
> an/(k*n)). Keeping these values apart, just the various blocks of a must be 
> evaluated each time (and multiplied and recomposed, of course).

For inspiration, I've dug up the karatsuba invariance code I have
lying around. Seems to have been written in 2007 (I thought it was
even older).

When an input a1 B + a0 is invarient, it precomputes a1 - a0 (the only
non-trivial evaluation in Karatsuba), and then it then recursively applies the
same precomputation to to the three numbers a1, a0 and |a1 - a0|,
until they fall below a threshold.

IIRC, it gave a modest improvmenent, of the order of 10%.

This idea of "recursive preevaluation" should be generalized to
include other methods than Karatsuba.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: karatsuba-invariance.c
Type: text/x-c-code
Size: 11032 bytes
Desc: not available
URL: <>

More information about the gmp-devel mailing list