FFT (snabb fouriertransform)
Algoritmen som delar upp en signal i sina frekvenser på n·log n steg i stället för n² — och därmed gjorde digital ljudbehandling praktiskt möjlig.
En diskret fouriertransform (DFT) räknad rakt av kostar n² multiplikationer: 1 024 sampel blir en miljon operationer. James Cooley och John Tukey publicerade 1965 en söndra-och-härska-variant som klyver problemet i halvor rekursivt och landar på ungefär tiotusen. Gauss hade i praktiken samma idé redan kring 1805, men skrev den på latin i en opublicerad anteckning, vilket inte hjälper så många.
I ljudvärlden finns FFT överallt: spektrumanalysatorn i en equalizer, brusreduktion, tidssträckning och snabb faltning, som är det enda skälet till att faltningsreverb med sekundlånga impulssvar går att köra i realtid. Biblioteket FFTW från MIT är fortfarande det man jämför sig med.