%快速傅立葉變換kqsfft（x）的源代碼
function c=kqsfft(x)
n1=length(x);
if(fix(log2(n1))<log2(n1))
    n2=fix(log2(n1))+1;
else
    n2=log2(n1);
end
n=2^n2;
x=[x zeros(1,(n-n1))];
q=0:n-1;
x(q+1)=x(daoxu(n)+1);
for m=1:n2
    le=2^m;
    le1=le/2;
    u=1;
    w=exp(-j*pi/le1);
    for m1=1:le1
        i=m1;
        while i<=n-1
            ip=i+le1;
            t=x(ip)*u;
            x(ip)=x(i)-t;
            x(i)=x(i)+t;
            i=i+le;
        end
        u=u*w;
    end
end
c=x;
end
 
 
function f=daoxu(n)
f=0:n-1;
p=0;j=0;
for i=0:n-1
    k=n/2;
    while j>=k
        j=j-k;
        k=k/2;
    end
    if j<k
        j=j+k;
    end
    if i<j
        p=f(i+2);
        f(i+2)=f(j+1);
        f(j+1)=p;
    end
end
f;
end