FFT (szybka transformata Fouriera)
Algorytm rozkładający sygnał na częstotliwości w n·log n krokach zamiast n² — co w ogóle umożliwiło praktyczną obróbkę cyfrowego dźwięku.
Policzona wprost dyskretna transformata Fouriera (DFT) kosztuje n² mnożeń: 1024 próbki to milion operacji. W 1965 roku James Cooley i John Tukey opublikowali wersję „dziel i zwyciężaj”, która rekurencyjnie połowi problem i sprowadza go do około dziesięciu tysięcy. Gauss miał w zasadzie ten sam pomysł około 1805 roku, ale zapisał go po łacinie w nieopublikowanej notatce, co nieco ograniczyło jego zasięg.
W audio jest wszędzie: wykres widma w korektorze, redukcja szumu, rozciąganie w czasie i szybki splot — jedyny powód, dla którego pogłos splotowy z wielosekundową odpowiedzią impulsową działa w czasie rzeczywistym. Biblioteka FFTW z MIT wciąż jest wzorcem, do którego porównuje się resztę.