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

[Torbjorn Granlund]

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
  > 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.
  
Do you also have FFT?  Then, what is the largest k ever used by the Toom
code?

  >   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.
  
That's very close to the ideal, which I suppose would be 21 bits for
that degree.  Cool.

-- 
Torbjörn