Toom-4.5 (aka Toom-5x4, Toom-6x3, Toom-7x2)
Paul Zimmermann
Paul.Zimmermann at loria.fr
Thu Oct 15 10:16:41 CEST 2009
> 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.
More information about the gmp-devel
mailing list