FFT (snelle fouriertransformatie)
Het algoritme dat een signaal in n·log n stappen in frequenties opdeelt in plaats van in n²: precies wat digitale audiobewerking in de praktijk mogelijk maakte.
Rechttoe rechtaan berekend kost een discrete fouriertransformatie (DFT) n² vermenigvuldigingen: 1024 samples betekent een miljoen bewerkingen. In 1965 publiceerden James Cooley en John Tukey een verdeel-en-heers-variant die het probleem steeds halveert en het terugbrengt tot ruwweg tienduizend. Gauss had rond 1805 in wezen hetzelfde idee, maar legde het vast in een ongepubliceerde Latijnse notitie, wat het bereik enigszins beperkte.
In audio is de FFT overal: het spectrumdisplay op een equalizer, ruisonderdrukking, time-stretching en snelle convolutie, de enige reden dat een convolutiereverb met een impulsresponsie van meerdere seconden in realtime kan draaien. De FFTW-bibliotheek van MIT blijft de maatstaf waaraan alle andere zich meten.