[SciPy-Dev] Fast sizes for FFT

[Sturla Molden]

On 24/12/14 14:25, Sri Krishna wrote:

> AFAIK the SciPy scipy.fftpack.fft function automatically does this. The
> function that calculates the next closest "composite number" isn't
> exposed, but any size you input to fftpack will automatically be resized
> to the next largest composite numbers for fast FFTs.

No, it factorizes the FFT into efficient chunks (size 2, 3, 4, or 5), 
and if the FFT size factorizes into larger primes it uses an O(N**2) DFT 
for those chunks. It allows us to compute FFTs of any size, but it will 
not always be efficient.

E.g. compare an FFT of size 4099 (prime) and compare with an FFT of size 
4096 (2**12).


In[10]: a = np.zeros(4099*100)

In[11]: %timeit scipy.fftpack.fft(a)
1 loops, best of 3: 615 ms per loop

In[12]: a = np.zeros(4096*100)

In[13]: %timeit scipy.fftpack.fft(a)
100 loops, best of 3: 8.64 ms per loop



Sturla