Numpy fft freezes for longer samples

Question

I'm currently playing with numpy.fft library. I have 200 .wav files with single notes, each around 4 seconds long. I run numpy.fft for each one by one but for samples that are 4.5 seconds or longer numpy.fft freezes. I don't understand why this happens? Also, if I explicitly specify the length of the fft the function works fine, but it detects wrong frequencies (it detects frequencies shifted by one or two semitones higher).

Here's my code:

(framerate, sample) = wav.read(wav_file)
monoChannel = sample.mean(axis=1)
fft_length = int(duration * framerate)     # duration is usually around 4sec long
FFT = numpy.fft(monoChannel, n=fft_length)

For samples where fft_length is smaller than 216090 numpy.fft works fine, for any longer fft, the algorithm hangs but it continues after I press ctrl+C in the terminal.

I'm using python 2.7.3

I'm new to FFT and I'd really like to understand what's going on here.

Answer 1

The FFT algorithm used in np.fft performs very well (meaning O(n log n)) when the input length has many small prime factors, and very bad (meaning a naive DFT requiring O(n^2)) when the input size is a prime number. See some example timings for powers of two and the next smallest prime:

In [69]: a = np.random.rand(1024)
In [70]: b = np.random.rand(1031)

In [71]: %timeit np.fft.fft(a)
10000 loops, best of 3: 20.8 µs per loop

In [72]: %timeit np.fft.fft(b)
100 loops, best of 3: 2.09 ms per loop

In [73]: a = np.random.rand(65536)
In [74]: b = np.random.rand(65537)

In [75]: %timeit np.fft.fft(a)
100 loops, best of 3: 3.16 ms per loop

In [76]: %timeit np.fft.fft(b)
1 loops, best of 3: 11.8 s per loop

For your particular case, note that:

216090 = 2 * 3**2 * 5 * 7**4
216091 = 216091 (prime)
216092 = 2**2 * 89 * 607

And consequently:

In [77]: %timeit np.fft.fft(np.random.rand(216090))
10 loops, best of 3: 37.1 ms per loop

In [78]: %timeit np.fft.fft(np.random.rand(216092))
10 loops, best of 3: 149 ms per loop

In [79]: %timeit np.fft.fft(np.random.rand(216091))
# Got bored and killed it before it finished, should take ~2 min
# based on the other results for prime numbers