Nearly Optimal Sparse Fourier Transform

Zimmermann Paul Paul.Zimmermann at
Tue Feb 7 13:05:05 CET 2012

       Hi Michael,

> MIT has a paper out on a new, faster sparse FFT algorithm. Is this
> applicable to multiplication in GMP?

I doubt it applies to GMP. In multiple-precision arithmetic, sparse numbers
do not happen usually, except when part of the inputs, for example when doing
arithmetic modulo 2^n+1. In this case special algorithms are used, with
usually O(n) complexity.

Paul Zimmermann

More information about the gmp-discuss mailing list