ToomN2 with "factored" evaluation
nisse at lysator.liu.se
Wed Nov 18 11:45:21 CET 2009
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
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...
Size: 11032 bytes
Desc: not available
More information about the gmp-devel