strange numpy fft performance

Question

During testing I have noticed something strange.

I’m FFT’ing a lot of vectors, and from time to time the numpy FFT function seemed to crash.

I briefly debugged this, and found that some vector lengths triggered the behavior.

By incident, I kept a script running, and to my surprise, it was not crashed, it simply took a little longer.

Does anyone have an idea of what is going on, and how to counter act this. I have seen this with many different FFT sizes, the below is an example only.

import numpy as np    
import time

a = np.zeros(166400)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

a = np.zeros(165039)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

a = np.zeros(165038)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

a = np.zeros(165036)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

a = np.zeros(165035)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

a = np.zeros(165034)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

a = np.zeros(165037)
start = time.time()
audio_fft = np.fft.fft(a,len(a))                          
print "it took %fs"%(time.time() -start)

print "done"

This outputs :

c:\Users\sol_sf\Desktop\math>fftTest.py
it took 0.029000s
it took 0.101000s
it took 0.176000s
it took 0.220000s
it took 0.671000s
it took 0.065000s
it took 369.132000s
done

c:\Users\sol_sf\Desktop\math>

Answer 1

A simple way to solve this - that isn't mentioned in the other answers - is to use scipy.fftpack.next_fast_len to pad the array. Given a target length, it gives you the next length > target that is a composite of 2, 3 and 5.

As the other answers have pointed out, FFT performs the worst when the array's length is a prime number. Its efficiency increases as the number of prime factors increase (2, 3, 5, etc.).