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

Stefan van der Walt stefan@sun.ac...
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 <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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: chirpz.py
Type: text/x-python
Size: 1135 bytes
Desc: not available
Url : http://projects.scipy.org/pipermail/scipy-user/attachments/20070207/73ba32a7/attachment.py
```