[SciPy-user] SciPy-user Digest, Vol 42, Issue 10
Wed Feb 7 08:42:46 CST 2007
On Feb 7, 2007, at 9:04 AM, firstname.lastname@example.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:
186888: 2 2 2 3 13 599
186890: 2 5 11 1699
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
More information about the SciPy-user