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

[Paul Zimmermann]

>   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).
> 
> This is slightly related to GMP's way of implementing Toom; we do it for
> some fixed polynomial degrees.  We haven't even contemplated the general
> Toom.

for the CADO-NFS project I have written some generic Toom-Cook k-way
(http://cado.gforge.inria.fr/). The evaluation and interpolation are
O(k^2), but it proved to be quite efficient.

>   We could also try a fixed-length FFT using double precision
>   numbers (assuming IEEE 754).
> 
> Is rigorous error analysis within reach for small enough FFT over
> doubles, or do you simply expect that it could be tested to better
> confidence?

according to Table 3.3 page 107 from [1], with an FFT of length 2^10 we can
store up to 19 bits in a double, which enables one to perform a 152-limb
product on a 64-bit computer. This is with a rigorous error analysis.

Paul

[1] Modern Computer Arithmetic, Richard Brent and Paul Zimmermann, version 0.3,    June 2009, http://www.loria.fr/~zimmerma/mca/mca-0.3.pdf.