Nearly Optimal Sparse Fourier Transform

Zimmermann Paul Paul.Zimmermann at loria.fr
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?
> 
> 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


More information about the gmp-discuss mailing list