БПФ (быстрое преобразование Фурье)
Алгоритм, раскладывающий сигнал на частоты за n·log n шагов вместо n², — именно он сделал цифровую обработку звука практичной.
В лоб дискретное преобразование Фурье (ДПФ) требует n² умножений: для 1024 отсчётов это миллион операций. В 1965 году Джеймс Кули и Джон Тьюки опубликовали вариант «разделяй и властвуй», который рекурсивно делит задачу пополам и сводит её примерно к десяти тысячам. Практически ту же идею Гаусс нашёл около 1805 года, но записал её по-латыни в неопубликованной заметке, что несколько ограничило её влияние.
В звуке БПФ повсюду: индикатор спектра на эквалайзере, шумоподавление, тайм-стретчинг и быстрая свёртка — единственная причина, по которой конволюционная реверберация с многосекундной импульсной характеристикой работает в реальном времени. Библиотека FFTW из MIT до сих пор остаётся эталоном для сравнения.