Matlab FFT (Fast Fourier Transform) function of non log-base2 numbers

Question

I have an app that I am developing that utalizes Apple's Accelerate Framework FFT function and I am trying to make it mimic the functionality of Matlab's FFT function. I have my current code set up to output exactly the same way as I am doing so in matlab. The only time that it doesn't output identically is when the number of elements in the data array are != a logarithm of base 2 (technically necessary for an FFT). I was wondering if anyone knew how the Matlab Function handled this case. If I do it using the apple code, it produces different results.

Note: I am not simply calling fft(x). I also FFT shift and take the absolute value and square it. I also mirror these in the apple code because they aren't directly affected by the FFT. They are called after the fact.

Example 1 - 16 Elements (Log base 2): Similar Output

Matlab Call:

x = 1:16;
Fxx = abs(fftshift(fft(x))).^2;

Fxx =

  Columns 1 through 7

64    66.5322    74.9807    92.5736    128    207.3490    437.0193

 Columns 8 through 14

1681.5451    18496    1682.5451    437.0193    207.3490    128    92.5736

  Columns 15 through 16

74.9807    66.5322

*Apple code omitted due to length

Apple Output:

Fxx[0] = 64.000000
Fxx[1] = 66.532232
Fxx[2] = 74.980664
Fxx[3] = 92.573612
Fxx[4] = 128.000000
Fxx[5] = 207.349044
Fxx[6] = 437.019336
Fxx[7] = 1681.545112
Fxx[8] = 18496.000000
Fxx[9] = 1681.545112
Fxx[10] = 437.019336
Fxx[11] = 207.349044
Fxx[12] = 128.000000
Fxx[13] = 92.573612
Fxx[14] = 74.980664
Fxx[15] = 66.532232

Example 2 - 10 Elements (NOT Log base 2): Different Output

Matlab Call:

x = 1:10;
Fxx = abs(fftshift(fft(x))).^2;

Fxx = 

Columns 1 through 7

25    27.6393    38.1966    72.3607    261.8034    3025    261.8034

Columns 8 through 10

72.3607    38.1966    27.6393

*Apple code omitted due to length

Apple Output:

Fxx[0] = 16.000000
Fxx[1] = 45.250000
Fxx[2] = 18.745166
Fxx[3] = 32.000000
Fxx[4] = 109.254834
Fxx[5] = 1296.000000
Fxx[6] = 109.254834
Fxx[7] = 32.000000
Fxx[8] = 18.745166
Fxx[9] = 45.250000

As you can see, they clearly produce the same output in the first example vs the second. I have tested with both positive and negative inputs and the only time they are different is when they are NOT log base 2. Does anyone know how Matlab handles this problem? Perhaps it fills the array with 0's until its a log base 2 number and then do the average of certain points? I have done lots of searching and cannot figure out what they do to obtain their output in this special case.

Answer 1

From the official MATLAB documentation:

The FFT functions (fft, fft2, fftn, ifft, ifft2, ifftn) are based on a library called FFTW.

To compute an N-point DFT when N is composite (that is, when N = N₁N₂), the FFTW library decomposes the problem using the Cooley-Tukey algorithm, which first computes N₁ transforms of size N₂, and then computes N₂ transforms of size N₁.

When N is a prime number, the FFTW library first decomposes an N-point problem into three (N – 1)-point problems using Rader's algorithm. It then uses the Cooley-Tukey decomposition described above to compute the (N – 1)-point DFTs.

I'm not sure how Apple's Accelerate Framework computes such FFTs, but I'm favouring MATLAB here to produce correct results.

Answer 2

This doesn't address your question, but I note that computing. Absolute value is a wasted operation if you are squaring the result. If speed is an issue, take that out. Also, instead of computing x^2 compute x*x. You get the same result faster. Don't know if the efficiency difference will be noticeable, but there's no point being computationally more expensive when cheaper is just as simple or simpler.