ToomN2 with "factored" evaluation

[Niels Möller]

Alberto Zanoni <zanoni at volterra.uniroma2.it> 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.

Regards,
/Niels

-------------- next part --------------
A non-text attachment was scrubbed...
Name: karatsuba-invariance.c
Type: text/x-c-code
Size: 11032 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20091118/23f6c593/attachment.bin>