zanoni at volterra.uniroma2.it
Wed Jun 10 14:46:08 CEST 2009
Alle 14:08, mercoledì 10 giugno 2009, David Harvey ha scritto:
> On Jun 10, 2009, at 3:00 AM, bodrato at mail.dm.unipi.it wrote:
> > There are a lot of tricks like this, the first one in Karatsuba
> > (due to?)
> > saving half an addition. There is one in Toom-3, saving half a sum
> > again,
> > and it is implemented in the current interpolate_5pts, another in
> > Toom-3.5, saving two half additions, implemented in interpolate_6pts.
> At some point I skimmed over your paper with Zanoni on the optimality
> of Toom-Cook matrices; I recall your automated search did not take
> into account these kind of tricks that merge the interpolation and
> recomposition stages. Is this correct?
Hi, I'm Alberto (Zanoni).
Yes, it is. The paper deals only with the interpolation stage. We didn't
consider its merging with evaluation and/or recomposition there.
> Have you tried this since
> writing the paper? It seems that it shouldn't be difficult in theory
> to extend the search method, although I have no idea if it's
> practical (the search spaces are very large...?).
Just to know, in our case the search space - for interpolation only - for
Toom-3.5 was analyzed in about one week of running time (while Toom-3 took
just some seconds).
It seems difficult to use the same tool from the very beginning of
interpolation phase with higher Toom. In our paper, for higher Toom
some "manual" steps had to be done, in order to have a sufficient number of
zero entries in the matrix, so that the analysis could be done in reasonable
This limitation was in practice the starting point to look for other
techniques searching for optimization or generalization somewhere else
(stages merging, use of the "divide by 2" technique, the "general" Toom using
powers of 2,...)
We didn't try to insert these techniques in our "old" automated search tool.
More information about the gmp-devel