function fft(X1);

N1=length(X1);
t=0;
while N1>1
    N1=N1/2;
    t=t+1;
end

N1=length(X1);
for n=1:N1
    X(n)=X1(n);
end 

if 2^t>N1
    for n=N1+1:2^t
        X(n)=0;
    end
end

N=length(X);
LH=N/2;
J=LH;
N1=N-2;
for I=1:N1
    if I<J
        T=X(I+1);
        X(I+1)=X(J+1);
        X(J+1)=T;
    end
    
    K=LH;
    while(J>=K)
        J=J-K;
        if mod(K,2)==0
            K=K/2;
        else K=(K-1)/2;
        end
    end
    J=J+K;
end


M=log2(N);
for i=1:N
    rCf(i)=cos(2*pi*(i-1)/N);
    iCf(i)=sin(2*pi*(i-1)/N);
end

for L=1:M
    B=floor(pow2(1,L-1)+0.5);
    for J=0:B-1
        p=J*(floor(pow2(1,M-L)+0.5));
        for K=J:(floor(pow2(1,L)+0.5)):N-1
            rPartKB=real(X(K+B+1))*rCf(p+1)-imag(X(K+B+1))*iCf(p+1);
            iPartKB=imag(X(K+B+1))*rCf(p+1)+real(X(K+B+1))*iCf(p+1);
            X(K+B+1)=(real(X(K+1))-rPartKB)+sqrt(-1)*(imag(X(K+1))-iPartKB);
            X(K+1)=(real(X(K+1))+rPartKB)+sqrt(-1)*(imag(X(K+1))+iPartKB);
        end
    end
end

real(X)-sqrt(-1)*imag(X)