function data=FFT(data,segno)
n=size(data,2);
// Realizza l'algoritmo di riordinamento descritto
// nel par. 3 delle note. Si noti che, rispetto alla
// notazione di quel paragrafo, i=k+1, j=j(k)+1
nhalf=n/2;
j=1;
for i=1:n
// Al primo passo di questo ciclo i=j=1=j(0), per cui l'unico
// effetto delle istruzioni seguenti e' di porre j=n/2+1=j(1)+1,
// il valore corrispondente a k=1, quindi a i=2. Al passo
// successivo viene effettuato lo scambio fra data(2) e data(j)
// e viene calcolato il valore di j corrispondente a i=3.
// Al passo i-esimo, viene effettuato lo scambio fra data(i) e
// data(j), ma solo se j>i, quindi viene calcolato il valore
// di j corrispondente a i+1.
    if(j>i) then
        temp=data(i);
        data(i)=data(j);
        data(j)=temp;
    end
m=nhalf;
while m>=2 & j>m
    j=j-m;
    m=m/2;
end
j=j+m;
end
// Calcola la TFD tramite l'algoritmo iterativo descritto
// nel paragrafo precedente. Si comincia con il calcolare
// le trasformate delle coppie di dati consecutivi, quindi
// si calcolano in successione quelle di ordine crescente,
// tramite un ciclo "while" controllato dalla variabile kmax,
// che assume i valori 1,2,4,8,...,n/2.
// Al passo k del ciclo "for" principale si calcolano le
// componenti di indice k e k+kmax delle n/(2*kmax) trasformate
// di ordine step=2*kmax, tramite un ciclo secondario.
kmax=1;
while n>kmax;
    step=2*kmax;
    w0=exp(-2*segno*%i*%pi/step);w=1;
    for k=1:kmax
        for i=k:step:n
            j=i+kmax;
            temp=data(j)*w;
            data(j)=data(i)-temp;
            data(i)=data(i)+temp;
        end
    w=w*w0;
    end
kmax=step;
end
endfunction
