Toom-4.5 (aka Toom-5x4, Toom-6x3, Toom-7x2)
tg at gmplib.org
Thu Oct 15 10:56:45 CEST 2009
Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:
> 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
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.
Do you also have FFT? Then, what is the largest k ever used by the Toom
> 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
according to Table 3.3 page 107 from , 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.
That's very close to the ideal, which I suppose would be 21 bits for
that degree. Cool.
More information about the gmp-devel