[SciPy-user] FFT speed ?

David Cournapeau david@ar.media.kyoto-u.ac...
Wed Feb 7 19:18:58 CST 2007

David Cournapeau wrote:
> Andrew Jaffe wrote:
>> It's probably worth pointing out that 186889 is, in fact, prime, 
>> which is certainly the worst case for any algorithm.
I went a bit further to see why it stuck on 186889. First, it only 
happens with numpy.fft.fft, not with scipy.fftpack. So fftw has nothing 
to do with it.

It seems like the fft used in numpy is really slow for prime number (eg 
N^2, which becomes quite big when your number is 186889...). One thing 
which could be done at least is to enable SIGINT to be sent to the 
function to abort it (It takes around 15 minutes to complete on my 

I guess the question is: is there any other implementation of fft usable 
for prime number in numpy ?


More information about the SciPy-user mailing list