Nearly Optimal Sparse Fourier Transform

[Zimmermann Paul]

       Hi Michael,

> MIT has a paper out on a new, faster sparse FFT algorithm. Is this
> applicable to multiplication in GMP?
> 
> http://arxiv.org/abs/1201.2501

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