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

Torbjorn Granlund tg at
Thu Oct 15 10:56:45 CEST 2009

Paul Zimmermann <Paul.Zimmermann at> 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
  ( 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
  > 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.


More information about the gmp-devel mailing list