Toom-4.5 (aka Toom-5x4, Toom-6x3, Toom-7x2)

[Paul Zimmermann]

       Hi,

> There are now more comprehensive diagrams.
> 
> I use green for 5 eval points, pink-violett for 6 eval points, red for 7
> eval points, and blue for 8 eval points.  Karatsuba also uses a shade of
> pink, since it is not close to the 6 point algorithms; the 4 point
> toom32 uses grey.  FFT use yellow/brown (FFT ng is not used by the
> measurement functions).

cool. By the way, it would be useful to say in the legend what FFT ng means.

> I wonder if some special DFT-based multiplication could compete with
> this toom foolery, to put a lower cap on # of eval points.  It does not
> necessarily need to use the FFT algorithm.

once thing I plan to do one day is to implement Schönhage-Strassen's algorithm
for a *fixed* transform length 2^k (in the current GMP code and in our new FFT
code, k is a parameter). Having k fixed should enable one to implement some
optimizations that are not possible (or tricky) for variable k. Since the cost
of a full FFT product is O(N^(k/(k-2))), we need at least k=5 (or 6) so that
it competes with the schoolbook algorithm. Indeed, k=5 gives O(N^1.667) and
k=6 gives O(N^1.5). We could also try a fixed-length FFT using double precision
numbers (assuming IEEE 754).

Paul