function c=fastft(x,n)
% c = fastft(x,n)
% Uses the fast Fourier transform method to compute the discrete Fourier 
% transform of a set of points
% inputs:
%	x - a set of 2^m points
%	n - the dimension of the vector x
% outputs:
%	c - the discrete Fourier transform



u=zeros(n/2,1);
v=zeros(n/2,1);
c=zeros(n,1);

if n==2
	c(1)=(x(1)+x(2))/2;
	c(2)=(x(1)-x(2))/2;
return
end


omega = exp(2*pi*i/n);

n=n/2;

for k=0:n-1
	u(k+1)=x(2*k+1);
	v(k+1)=x(2*k+2);
end

ftu=fastft(u,n);
ftv=fastft(v,n);
for k=1:n
	c(k)=(ftu(k) + omega^(-(k-1))*ftv(k))/2;
	c(k+n)=(ftu(k) - omega^(-(k-1))*ftv(k))/2;
end






