FFT (transformada rápida de Fourier)
El algoritmo que descompone una señal en sus frecuencias en n·log n pasos en lugar de n², y que hizo viable el procesamiento digital de audio.
Calculada a lo bruto, una transformada discreta de Fourier (DFT) cuesta n² multiplicaciones: 1.024 muestras son un millón de operaciones. En 1965, James Cooley y John Tukey publicaron una versión de divide y vencerás que parte el problema por la mitad de forma recursiva y lo deja en unas diez mil. Gauss había tenido en esencia la misma idea hacia 1805, pero la dejó en latín en una nota inédita, lo que no ayudó mucho a su difusión.
En audio está en todas partes: el analizador de espectro de un ecualizador, la reducción de ruido, el estiramiento temporal y la convolución rápida, única razón por la que una reverberación por convolución con respuestas al impulso de varios segundos puede funcionar en tiempo real. La biblioteca FFTW, del MIT, sigue siendo la referencia con la que todos se comparan.