[SciPy-user] SciPy-user Digest, Vol 42, Issue 10
Stefan van der Walt
Wed Feb 7 11:34:32 CST 2007
On Wed, Feb 07, 2007 at 12:20:13PM -0500, Anne Archibald wrote:
> On 07/02/07, Paul Ray <email@example.com> wrote:
> > 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:
> > >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).
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 1135 bytes
Desc: not available
Url : http://projects.scipy.org/pipermail/scipy-user/attachments/20070207/73ba32a7/attachment.py
More information about the SciPy-user