FFT WITHOUT Built-in functions

How do I write the matlab code for fourier transform without the built-in function (fft). NOT DFT! Decimation in time radix-2fft please!

Answer 1

[Dyuman Joshi]

Using the definition given at the end of FFT document

%x is your input
x=[1 2 3 4];
fft(x) %using for comparison

ans = 
  10.0000 + 0.0000i  -2.0000 + 2.0000i  -2.0000 + 0.0000i  -2.0000 - 2.0000i

Method 1

%loop approach
for j=1:numel(x)
    y(j)=sum(arrayfun(@(z) x(z)*exp(-i*2*pi*(j-1)*(z-1)/numel(x)),1:numel(x)));
end
y

y = 
  10.0000 + 0.0000i  -2.0000 + 2.0000i  -2.0000 - 0.0000i  -2.0000 - 2.0000i

Method 2

%vector approach
l=length(x);
z = x*exp(-2j*pi/l*(0:l-1).'*(0:l-1))

z = 
  10.0000 + 0.0000i  -2.0000 + 2.0000i  -2.0000 - 0.0000i  -2.0000 - 2.0000i

[Camille Pham]

Without the fft built in function.

[Dyuman Joshi]

@Camille Pham, y and z are obtained without using fft(), I just used fft() to show the comparison.