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