FFT (trasformata di Fourier veloce)
L'algoritmo che scompone un segnale nelle sue frequenze in n·log n passi invece di n², e che ha reso davvero praticabile l'elaborazione audio digitale.
Calcolata in modo ingenuo, la trasformata di Fourier discreta (DFT) costa n² moltiplicazioni: 1.024 campioni significano un milione di operazioni. Nel 1965 James Cooley e John Tukey pubblicarono una versione «divide et impera» che dimezza ricorsivamente il problema e lo riduce a circa diecimila. Gauss aveva avuto sostanzialmente la stessa idea intorno al 1805, ma l'aveva annotata in latino in un appunto mai pubblicato, il che ne limitò un poco la diffusione.
Nell'audio è ovunque: il display dello spettro su un equalizzatore, la riduzione del rumore, il time-stretching e la convoluzione veloce, l'unico motivo per cui un riverbero a convoluzione con una risposta all'impulso di diversi secondi può girare in tempo reale. La libreria FFTW del MIT resta il riferimento con cui tutte le altre si confrontano.