On Feb 7, 2007, at 9:04 AM, scipy-user-request@scipy.org wrote:
I have a problem with fft speed.
The speed of most FFT algorithms depends greatly on the largest prime factor of N. Here are the factors of your example numbers:
factor 186888 186888: 2 2 2 3 13 599
factor 186890 186890: 2 5 11 1699
factor 186889 186889: 186889
Note that 186889 is prime! This is the worst case situation! Numbers which are powers of 2 can be FFT'ed in order N*Log_2(N) time, while prime numbers take order N**2 time. This is what you are seeing. You might do a survey of FFT algorithms to see which ones perform best on prime Ns. Many you will find, work ONLY on power of 2 Ns! You should make sure that your SciPy is using FFTW3 for the FFT engine for sure, since I think it does about as well as possible on prime Ns. You can read about FFTW at http://fftw.org I rarely use FFT in SciPy/NumPy since there are many confusing statements in the instructions about FFTW2/FFTW3 support which don't make sense. The API changed from FFTW2 to FFTW3 and it is really important to get this right. I think FFTW2 support should be removed and someone should do a check to make sure the FFTW3 support is implemented correctly. Cheers, -- Paul