Toom-4.5 (aka Toom-5x4, Toom-6x3, Toom-7x2)
Torbjorn Granlund
tg at gmplib.org
Thu Oct 15 09:50:53 CEST 2009
Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:
> 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.
Perhaps we just know it is "next generation" and have yet to figure out
how it should work? :-)
> 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).
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.
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?
--
Torbjörn
More information about the gmp-devel
mailing list