Optimizing Fourier transformed signal length

Question

I recently stumbled on an interessting problem, when computing the fourier transform of a signal with np.fft.fft. The reproduced problem is:

%timeit np.fft.fft(np.random.rand(59601))    
1 loops, best of 3: 1.34 s per loop

I found that the amount of time is unexpectedly long. For instance lets look at some other fft's, but with a slightly longer/shorter signal:

%timeit np.fft.fft(np.random.rand(59600))
100 loops, best of 3: 6.18 ms per loop

%timeit np.fft.fft(np.random.rand(59602))
10 loops, best of 3: 61.3 ms per loop

%timeit np.fft.fft(np.random.rand(59603))
10 loops, best of 3: 113 ms per loop

%timeit np.fft.fft(np.random.rand(59604))
1 loops, best of 3: 182 ms per loop

%timeit np.fft.fft(np.random.rand(59605))
100 loops, best of 3: 6.53 ms per loop

%timeit np.fft.fft(np.random.rand(59606))
1 loops, best of 3: 2.17 s per loop

%timeit np.fft.fft(np.random.rand(59607))
100 loops, best of 3: 8.14 ms per loop

We can observe that the times are now in miliseconds, except for np.random.rand(59606), which lasts 2.17 s.

Note, the numpy documentation states:

FFT (Fast Fourier Transform) refers to a way the discrete Fourier Transform (DFT) can be calculated efficiently, by using symmetries in the calculated terms. The symmetry is highest when n is a power of 2, and the transform is therefore most efficient for these sizes.

However these vectors do not have the length of a power of 2. Could someone explain how to avoid/predict cases, when computation times are considerably higher?

59601 is 3*19867, and 19867 is prime. See http://stackoverflow.com/questions/21161033/strange-numpy-fft-performance — Warren Weckesser, Jan 22 '16 at 14:07
Also, 59606 is 2*29803, and 29803 is prime. For a really slow case, try 59611, which is prime. — Warren Weckesser, Jan 22 '16 at 14:14

score 3 · Accepted Answer · answered Jan 22 '16 at 15:13

As some comments have pointed, the prime factor decomposition allows you to predict the time to calculate the FFT. The following graphs show your results. Remark the logarithmic scale!

This image is generated with the following code:

import numpy as np
import matplotlib.pyplot as plt

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    #from http://stackoverflow.com/questions/23287/largest-prime-factor-of-a-number/412942#412942
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1

    return factors


times = []
decomp = []
for i in range(59600, 59613):
    print(i)
    t= %timeit -o np.fft.fft(np.random.rand(i))
    times.append(t.best)
    decomp.append(max(prime_factors(i)))

plt.loglog(decomp, times, 'o')
plt.ylabel("best time")
plt.xlabel("largest prime in prime factor decomposition")
plt.title("FFT timings")

Optimizing Fourier transformed signal length

1 Answers1