On Wed, Feb 07, 2007 at 12:20:13PM -0500, Anne Archibald wrote:
On 07/02/07, Paul Ray <paul.ray@nrl.navy.mil> wrote:
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
There are at least two algorithms to efficiently compute prime-length FFTs (Rader's conversion and the chirp-z transform).
Here is a rough implementation (I don't guarantee anything). Cheers Stéfan