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

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?

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.

• Hi hotpaw2, sorry I forgot to mention that I am using matlab FFT, does that make any difference? thank you again. Jul 24, 2013 at 16:37
• Matlab may use a modern FFT library, such as FFTW, internally. Check the matlab documentation for your version. Jul 24, 2013 at 16:51
• Also, @hotpaw2, I am using fftshift already... Jul 24, 2013 at 16:51
• With fftshift, put the data windows center where you want to measure phase. Or calculate phase from the center backwards in time using a good frequency estimation. Jul 24, 2013 at 16:54

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}$.

• Thank you user4619 for the answers, 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? Jul 24, 2013 at 17:04
• Also, @user4619, since you mentioned that yes the phase angle could change, which one should I trust that is giving me the correct answer? (i do not know the phase angle before hand or the amplitude, i only know the frequency before hand)...thank you Jul 24, 2013 at 17:05
• @lamia Power-of-2 is only for speed issues. That is it. There is nothing magical about it otherwise. About the phase angle - remember that even though your phase angle changes, so does your peak frequency. If you perform an FFT of 1000 points, you pick frequency bin 100 as the peak, and find its phase angle. That is correct. Then you perform an FFT of 343212 points, and pick a frequency 34321 as the peak, and it has a different phase angle. That is still correct. "Phase" is a function of frequency. (If you found this helpful please feel free to upvote) Jul 24, 2013 at 17:27
• @lamia Also see my edits. Jul 24, 2013 at 17:35
• Thank you so much for the explanations you have provided :) Jul 29, 2013 at 15:43

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.