How important is it to use power of 2 when using FFT?

Question

Here is the problem. I have a 2D array of data, first column represents the time data and the second column represents the sinusoidal response data, based on the time data. I apply fft and I get my frequency (that I started with) in a specific bin as I expected and I find the amplitude and phase angle from that bin. Now the problem is I have the same set up but with more data points, I apply the fft again and the bin number changes (which is normal and it is where I expect it to be), the amplitude is the same but the phase angle is different) first is this normal? second, what approach should I take? Thank you

PS: neither of the set ups (mentioned above) give data of length of power of 2, say the first one gives 1620 data points and the second one gives 1745 data points, so should be taking the next power of 2 for both from the beginning?

Answer 1

Modern FFT libraries, such as FFTW and Apple's Accelerate framework can do non-power-of-2 FFTs very efficiently, as long as all the prime divisors of the composite length are fairly small (2,3,5,etc.)

A power of 2 makes it simpler (about 1 page of source code) if you have to code your own FFT for some reason, or are otherwise constrained as to max program length (or FPGA gates, etc.)

For phase measurement, it might be easier to do an fftshift (pre-rotate the data by N/2) to reference FFT phase to the center of the data window, where the evenness/oddness ratio, and thus the phase won't change or alternate with bin number (for phase that is the same at the center of that data window) even for signals that are non-periodic in the FFT length, as you vary the length.

Answer 2

There is nothing inherently 'magical' about performing a power of 2 DFT, other than the fact that performing a power of 2 DFT allows one to perform the DFT in $O(Nlog(N))$ instead of $O(N^2)$. So the power of 2 DFT, (The algorithm that does this is known as the FFT), allows you to simply speed up your DFT computation by a huge factor.

I apply the fft again and the bin number changes (which is normal and it is where I expect it to be), the amplitude is the same but the phase angle is different) first is this normal?

If you do a larger DFT than your data vector, you are essentially going to be interpolating in the frequency domain. Thus, your new peak might not be the old equivalent peak that you first detected, before you took a larger DFT. And since it is not the same, you are essentially choosing a different complex exponential (sine plus cosine) basis this time around, meaning you would likely have a different phase value, yes.

PS: neither of the set ups (mentioned above) give data of length of power of 2, say the first one gives 1620 data points and the second one gives 1745 data points, so should be taking the next power of 2 for both from the beginning?

Yes, if you want to take a power of 2 FFT, then you would simply chose the next power of 2 length FFT that is larger than your data record length.

i dont necessarily want or not want to take the power of 2 FFT (time performance is not my issue at all), more like, do I need to?

You should never take an FFT of length less than your record length, unless you want to discard data. The question of "How big does my FFT need to be", assuming the FFT length is larger than your data record length, then quickly becomes application dependent. Usually you can get away with an FFT length the same as your record length. However, sometimes you want to pick a peak from a 'smoother' FFT. In this case, you can take a larger FFT length, (2 times more, 3 times more, 10 times more, etc), and you would have interpolated your peak in the frequency domain. There is no magic number, however. Remember that the granularity of your FFT result is always $\frac{f_s}{N}$.

Answer 3

Showing @user4619's answer:

Using IPython, which is similar to Matlab

In[1]: fft(arange(2**22))
1 loops, best of 3: 354 ms per loop

In[2]: fft(arange(4*1000*90*12)) # close to 2**22
# equal to 2*2 * 2*5*2*5*2*5 * 3*3*2*5 * 2*2*3
1 loops, best of 3: 295 ms per loop

In[2]: fft(arange(2**22+1))
1 loops, best of 3: 14 s per loop

If you're using really prime numbers, rather important (a factor of 50!). If you're using numbers that have low factors, not important. But doing it with only prime numbers only does it faster -- it doesn't change the answer at all.