title: Help with EXCEL Fast Fourier Transform
body: <p>I am trying to use Excel's (2007) built in FFT feature, however, it requires that I have 2^n data points - which I do not have.</p>
  
  <p>I have tried two things, both give different results:</p>
  
  <ol>
  <li>Pad the data values by zeros so that N (the number of data points) reach the closest power of 2 </li>
  <li>Use a divide-and-conquer approach i.e. if I have 112 data points, then I do a FFT for 64, then 32, then 16 (112=64+32+16)</li>
  </ol>
  
  <p>Which is the better approach? I am comfortable writing VBA macros but I am looking for an algorithm which does not require the constraint of N being power of 2. Can anyone help?</p>