# fft is unusable of moderately large arrays with a size which is a prime number (Trac #506) #1104

Closed
opened this issue Oct 19, 2012 · 7 comments

### numpy-gitbot commented Oct 19, 2012

Original ticket http://projects.scipy.org/numpy/ticket/506 on 2007-04-27 by @cournape, assigned to unknown.

Currently, using fft on arrays of size which has a prime number is extremely slow (up to 15 minutes for eg an array of size 100003). The major problem though is that the code being uninterruptible, this effectively kills the current python session. My understanding is that the fft in numpy is using fftpack converted in C, which uses a O(N^2) algorithm for prime numbers ? Would it be possible at least to make the code interruptible ?

{{

# !python

import numpy as N
from scipy import fftpack

# prime is a prime number

prime = 100003

a = N.random.randn(prime)

print 'scipy computing...'
fftpack.fft(a)

print 'numpy computing...'
N.fft.fft(a)
}}

Author

### numpy-gitbot commented Oct 19, 2012

 Attachment added by @cournape on 2007-04-27: interruptible_fft.patch
Author

### numpy-gitbot commented Oct 19, 2012

 @cournape wrote on 2007-04-27 I attached a patch which solves the interruptible part.
Author

### numpy-gitbot commented Oct 19, 2012

 @alberts wrote on 2007-05-12 Looks like the interruptible patch at least can be applied for 1.0.3. After that the milestone should probably be updated to address the rest of the issue in a next release.
Author

### numpy-gitbot commented Oct 19, 2012

 Milestone changed to `1.0.3 Release` by @alberts on 2007-05-12
Author

### numpy-gitbot commented Oct 19, 2012

 @charris wrote on 2007-05-12 As far as I know, there is no fast algorithm for the prime numbers other than fast convolution, i.e., http://en.wikipedia.org/wiki/Bluestein's_FFT_algorithm. As Bluestein's algorithm also works for the chirp-z transform we might prefer to implement the latter, or maybe put it in scipy.
Author

### numpy-gitbot commented Oct 19, 2012

 @charris wrote on 2007-05-13 Davids patch works for me, so I am going to commit the patch and close the bug. Making a fast transform for a prime number of elements is an enhancement. We probably need a chirp-z transform, either in numpy or in scipy, but its current lack is not a bug.
Author

### numpy-gitbot commented Oct 19, 2012

 @stefanv wrote on 2007-05-13 According to http://www.fftw.org/fftw-paper-ieee.pdf FFTW implements Bluestein's algorithm. A python implementation is available at http://www.mail-archive.com/numpy-discussion@scipy.org/msg01812.html
referenced this issue Oct 19, 2012
referenced this issue Oct 23, 2012
referenced this issue Nov 13, 2018