[SciPy-user] SciPy-user Digest, Vol 42, Issue 10

Paul Ray paul.ray@nrl.navy....
Wed Feb 7 08:42:46 CST 2007

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.


-- Paul

More information about the SciPy-user mailing list