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

[Torbjorn Granlund]

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