Toom symmetries

David Harvey dmharvey at
Wed Jun 10 14:08:54 CEST 2009

On Jun 10, 2009, at 3:00 AM, bodrato at 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[1] 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? 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...?).


More information about the gmp-devel mailing list