[Numpy-tickets] [NumPy] #506: fft is unusable of moderately large arrays with a size which is a prime number

[NumPy]

#506: fft is unusable of moderately large arrays with a size which is a prime
number
-----------------------+----------------------------------------------------
 Reporter:  cdavid     |       Owner:  somebody
     Type:  defect     |      Status:  new     
 Priority:  normal     |   Milestone:          
Component:  numpy.fft  |     Version:  devel   
 Severity:  major      |    Keywords:          
-----------------------+----------------------------------------------------
 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)
 }}

-- 
Ticket URL: <http://projects.scipy.org/scipy/numpy/ticket/506>
NumPy <http://projects.scipy.org/scipy/numpy>
The fundamental package needed for scientific computing with Python.