function x = algo_fft_1D(x)

N = length(x);
%
% disposizione dei dati in ordine ad inversione dei bit
j=0;
for n=0:N-1
  %disp(['n=' dec2bin(n,log2(N)) '   j=' dec2bin(j,log2(N))]);
  if j > n
    temp = x(j+1);
    x(j+1) = x(n+1);
    x(n+1) = temp;
  end;
  % calcolo il prossimo "j"
  k = N/2;
  while k <= j
    j = j - k;
    k = k / 2;
  end;
  j = j + k;
end;
%
% calcolo "sul posto" della sequenza trasformata  NB: qui "i" e "j" sono usate come variabili !
for k=1:log2(N)
  u = complex(1,0);
  w = complex(cos(pi/2^(k-1)),-sin(pi/2^(k-1)));
  for j=1:2^(k-1)
    for i=j:2^k:N-1
      % calcolo della farfalla
      ip = i + 2^(k-1);
      %disp(['i=' num2str(i) '  ip=' num2str(ip) '  u=' num2str(u)]);
      temp = x(ip) * u;
      x(ip) = x(i) - temp;
      x(i) = x(i) + temp;
    end;
    u = u * w;
  end;
end;


