b'\n_START_ARTICLE_\nTrasformata di Fourier veloce\n_START_PARAGRAPH_\nIn matematica, la trasformata di Fourier veloce, spesso abbreviata con FFT (dall\'inglese Fast Fourier Transform), \xc3\xa8 un algoritmo ottimizzato per calcolare la trasformata discreta di Fourier (DFT) o la sua inversa._NEWLINE_La FFT \xc3\xa8 utilizzata in una grande variet\xc3\xa0 di applicazioni, dall\'elaborazione di segnali digitali alla soluzione di equazioni differenziali alle derivate parziali agli algoritmi per moltiplicare numeri interi di grandi dimensioni grazie al basso costo computazionale.\n_START_SECTION_\nAlgoritmo di Cooley-Tukey\n_START_PARAGRAPH_\nL\'algoritmo FFT pi\xc3\xb9 diffuso \xc3\xa8 l\'algoritmo di Cooley-Tukey. Questo algoritmo si basa sul principio di divide et impera, e spezza ricorsivamente una DFT di qualsiasi dimensione , con  numero composto tale che  in DFT pi\xc3\xb9 piccole di dimensioni  e , insieme a  moltiplicazioni per l\'unit\xc3\xa0 immaginaria, detti fattori twiddle._NEWLINE_Questo metodo (e in generale l\'idea di una trasformata di Fourier veloce) fu reso popolare da una pubblicazione di James William Cooley e John Wilder Tukey nel 1965, ma in seguito si scopr\xc3\xac che i due autori avevano indipendentemente reinventato un algoritmo noto a Carl Friedrich Gauss nel 1805  (e successivamente riscoperto in molte altre forme limitate)._NEWLINE_L\'uso pi\xc3\xb9 conosciuto dell\'algoritmo di Cooley-Tukey \xc3\xa8 di dividere e trasformare in due pezzi di  ad ogni passo, ed \xc3\xa8 quindi ottimizzato solo per dimensioni che siano potenze di due, ma in generale pu\xc3\xb2 essere utilizzata qualsiasi fattorizzazione (com\'era noto sia a Gauss che a Cooley e Tukey). Questi casi sono chiamati rispettivamente casi radice 2 e radice mista (ma esistono anche altri approcci con nomi specifici). Anche se l\'idea di base \xc3\xa8 ricorsiva, la gran parte delle implementazioni tradizionali riorganizzano l\'algoritmo per evitare la ricorsione esplicita. Inoltre, poich\xc3\xa9 l\'algoritmo di Cooley-Tukey spezza la DFT in DFT pi\xc3\xb9 piccole, pu\xc3\xb2 essere arbitrariamente combinato con qualsiasi altro algoritmo per la DFT, come quelli descritti qui sotto._NEWLINE_Un\'implementazione iterativa in C++ della FFT basata sull\'algoritmo di Cooley-Tukey \xc3\xa8 la seguente:_NEWLINE_#include <iostream>#include <complex>#define MAX 200using namespace std;int log2(int N)    //funzione per calcolare il logaritmo in base 2 di un intero{_NEWLINE_  int k = N, i = 0;_NEWLINE_  while(k) {_NEWLINE_    k >>= 1;_NEWLINE_    i++;_NEWLINE_  }_NEWLINE_  return i - 1;}int check(int n)    //usato per controllare se il numero di componenti del vettore di input \xc3\xa8 una potenza di 2{_NEWLINE_  return n > 0 && (n & (n - 1)) == 0;}int reverse(int N, int n)    //calcola il reverse number di ogni intero n rispetto al numero massimo N{_NEWLINE_  int j, p = 0;_NEWLINE_  for(j = 1; j <= log2(N); j++) {_NEWLINE_    if(n & (1 << (log2(N) - j)))_NEWLINE_      p |= 1 << (j - 1);_NEWLINE_  }_NEWLINE_  return p;}void ordina(complex<double>* f1, int N)     //dispone gli elementi del vettore ordinandoli per reverse order{_NEWLINE_  complex<double> f2[MAX];_NEWLINE_  for(int i = 0; i < N; i++)_NEWLINE_    f2[i] = f1[reverse(N, i)];_NEWLINE_  for(int j = 0; j < N; j++)_NEWLINE_    f1[j] = f2[j];}void transform(complex<double>* f, int N)     //calcola il vettore trasformato{_NEWLINE_  ordina(f, N);    //dapprima lo ordina col reverse order_NEWLINE_  complex<double> W[N / 2]; //vettore degli zeri dell\'unit\xc3\xa0._NEWLINE_                            //Prima N/2-1 ma genera errore con ciclo for successivo_NEWLINE_                           //in quanto prova a copiare in una zona non allocata "W[N/2-1]"_NEWLINE_  W[1] = polar(1., -2. * M_PI / N);_NEWLINE_  W[0] = 1;_NEWLINE_  for(int i = 2; i < N / 2; i++)_NEWLINE_    W[i] = pow(W[1], i);_NEWLINE_  int n = 1;_NEWLINE_  int a = N / 2;_NEWLINE_  for(int j = 0; j < log2(N); j++) {_NEWLINE_    for(int i = 0; i < N; i++) {_NEWLINE_      if(!(i & n)) {_NEWLINE_        /*ad ogni step di raddoppiamento di n, vengono utilizzati gli indici */_NEWLINE_        /*\'i\' presi alternativamente a gruppetti di n, una volta si e una no.*/_NEWLINE_        complex<double> temp = f[i];_NEWLINE_        complex<double> Temp = W[(i * a) % (n * a)] * f[i + n];_NEWLINE_        f[i] = temp + Temp;_NEWLINE_        f[i + n] = temp - Temp;_NEWLINE_      }_NEWLINE_    }_NEWLINE_    n *= 2;_NEWLINE_    a = a / 2;_NEWLINE_  }}void FFT(complex<double>* f, int N, double d){_NEWLINE_  transform(f, N);_NEWLINE_  for(int i = 0; i < N; i++)_NEWLINE_    f[i] *= d; //moltiplica il vettore per il passo in modo da avere il vettore trasformato effettivo}int main(){_NEWLINE_  int n;_NEWLINE_  do {_NEWLINE_    cout << "specifica la dimensione del vettore,che sia potenza di 2" << endl;_NEWLINE_    cin >> n;_NEWLINE_  } while(!check(n));_NEWLINE_  double d;_NEWLINE_  cout << "inserisci la dimensione del passo di campionamento" << endl;_NEWLINE_  cin >> d;_NEWLINE_  cout << "passo di campionamento = " << d << endl;_NEWLINE_  complex<double> vec[MAX];_NEWLINE_  cout << "inserisci il vettore di campionamento" << endl;_NEWLINE_  for(int i = 0; i < n; i++) {_NEWLINE_    cout << "inserisci la componente di indice " << i << endl;_NEWLINE_    cin >> vec[i];_NEWLINE_    cout << "indice " <<i<< "= " << vec[i]  << endl;_NEWLINE_  }_NEWLINE_  FFT(vec, n, d);_NEWLINE_  cout << "vettore trasformato" << endl;_NEWLINE_  for(int j = 0; j < n; j++)_NEWLINE_    cout << vec[j] << endl;_NEWLINE_  return 0;}\n_START_SECTION_\nAltri algoritmi per calcolare la FFT\n_START_PARAGRAPH_\nCi sono altri algoritmi per la FFT oltre al Cooley-Tukey. Per N=N\xe2\x82\x81N\xe2\x82\x82 con N\xe2\x82\x81 e N\xe2\x82\x82 numeri coprimi pu\xc3\xb2 essere utilizzato l\'algoritmo di Good-Thomas PFA (Prime-factor FFT Algorithm), basato sul teorema cinese del resto, che fattorizza la DFT in un modo simile al Cooley-Tukey. L\'algoritmo FFT di Rader-Brenner \xc3\xa8 un sistema di fattorizzazione simile al Cooley-Tukey ma con fattori twiddle immaginari puri, riducendo il numero delle moltiplicazioni al costo di un aumento delle addizioni e della instabilit\xc3\xa0 numerica._NEWLINE_Gli algoritmi che suddividono ricorsivamente la DFT in operazioni pi\xc3\xb9 piccole diverse dalla DFT includono l\'algoritmo di Bruun e il QFT. (Gli algoritmi di Rader-Brenner e il QFT sono stati proposti per dimensioni che siano potenze di 2, ma \xc3\xa8 possibile che vengano adattati per numeri composti qualunque. L\'algoritmo di Bruun si pu\xc3\xb2 applicare su dimensioni qualunque anche composte). In particolare l\'algoritmo per la FFT di Bruun \xc3\xa8 basato sull\'interpretare la FFT come la fattorizzazione ricorsiva del polinomio z\xe2\x81\xbf-1 in polinomi a coefficienti reali nella forma z\xe1\xb5\x90-1 e z\xc2\xb2\xe1\xb5\x90+az\xe1\xb5\x90+1._NEWLINE_Un altro punto di vista polinomiale \xc3\xa8 sfruttato dall\'algoritmo FFT di Winograd, che fattorizza z\xe2\x81\xbf-1 in polinomi ciclotomici, che spesso hanno coefficienti 1, 0 o \xe2\x88\x921, e quindi richiedono poche (se non nessuna) moltiplicazione, quindi pu\xc3\xb2 essere utilizzato per ottenere FFT con un numero minimo di moltiplicazioni ed \xc3\xa8 spesso usato per trovare algoritmi efficienti per piccoli fattori. In effetti Winograd dimostr\xc3\xb2 che la DFT pu\xc3\xb2 essere calcolata con solo O(n) moltiplicazioni; sfortunatamente questo si ottiene con un numero considerevolmente superiore di addizioni, uno scambio non pi\xc3\xb9 favorevole sui moderni processori dotati di chip dedicati per le moltiplicazioni in virgola mobile. In particolare, l\'algoritmo di Winograd fa anche uso dell\'algoritmo PFA e di quello di Rader per le FFT con dimensioni che siano numeri primi._NEWLINE_Un altro algoritmo FFT per numeri primi \xc3\xa8 dovuto a L. I. Bluestein ed \xc3\xa8 a volte chiamata algoritmo chirp-z: riesprime la DFT come una convoluzione, la cui dimensione pu\xc3\xb2 essere portata ad una potenza di due e valutata dalla FFT di Cooley-Tukey.\n_START_SECTION_\nAccuratezza e approssimazioni\n_START_PARAGRAPH_\nTutti gli algoritmi FFT presentati finora calcolano esattamente la DFT (in senso aritmetico, trascurando cio\xc3\xa8 gli errori dovuti ai calcoli in virgola mobile). Tuttavia sono stati anche proposti algoritmi FFT che calcolano la DFT approssimativamente, con un errore che pu\xc3\xb2 essere reso arbitrariamente piccolo al costo di un maggiore sforzo computazionale. Questi algoritmi scambiano l\'errore di approssimazione a favore di una maggiore velocit\xc3\xa0 od altre caratteristiche. Alcuni esempi sono l\'algoritmo FFT di Edelman et al. (1999), la FFT di Guo e Barrus (1996) basata sui wavelet o quella di Shentov et al. (1995)._NEWLINE_Anche gli algoritmi FFT "esatti" hanno degli errori quando viene utilizzata l\'aritmetica a virgola mobile a precisione finita, ma questi errori sono in genere molto piccoli; la maggior parte degli algoritmi FFT hanno eccellenti propriet\xc3\xa0 numeriche. Il limite superiore dell\'errore relativo per l\'algoritmo di Cooley-Tukey \xc3\xa8 O(\xce\xb5 log n), contro O(\xce\xb5 n3/2) per la formula originaria della DFT (Gentleman e Sande, 1966). Questi risultati, comunque, sono molto sensibili verso l\'accuratezza dei fattori twiddle usati nella FFT (che sono poi i valori delle funzioni trigonometriche), e non \xc3\xa8 raro che implementazioni poco accurate della FFT abbiano precisione molto peggiori, ad esempio se utilizzano tabelle dei valori trigonometrici poco accurate. Alcuni algoritmi di FFT, come il Rader-Brenner, sono intrinsecamente meno stabili._NEWLINE_In aritmetica a virgola fissa, la precisione degli errori accumulati dagli algoritmi di FFT sono peggiori, e crescenti come O(\xe2\x88\x9an) per l\'algoritmo di Cooley-Tukey. Inoltre, raggiungere questa precisione richiede un\'accurata attenzione e nello riscalare i fattori per minimizzare la perdita di precisione, e gli algoritmi di FFT in virgola fissa richiedono il riscalamento ad ogni stadio intermedio delle decomposizioni come nel Cooley-Tukey._NEWLINE_Per verificare la correttezza di un\'implementazione di un algoritmo FFT, garanzie rigorose possono essere ottenute in tempo O(n log n) con una semplice procedura che controlla le propriet\xc3\xa0 di linearit\xc3\xa0, della risposta impulsiva e della tempo-invarianza per dati in input casuali.'