FFT（高速フーリエ変換）
信号を周波数成分に分解する計算をn²ではなくn·log n回で済ませるアルゴリズム。デジタル音声処理が実用になったのは、これのおかげだ。
素朴に離散フーリエ変換（DFT）を計算すると乗算がn²回かかる。1,024サンプルなら100万回だ。1965年、ジェームズ・クーリーとジョン・テューキーが、問題を再帰的に半分にしていく分割統治版を発表し、これを約1万回にまで減らした。ガウスは1805年頃に本質的に同じ着想を得ていたが、未発表のラテン語のメモに書いただけだったため、広まりようがなかった。
音声処理ではあらゆる場所に現れる。イコライザーのスペクトラム表示、ノイズ除去、タイムストレッチ、そして高速畳み込みだ。数秒のインパルス応答を持つコンボリューション・リバーブがリアルタイムで動くのは、高速畳み込みがあるからにほかならない。MITのFFTWライブラリは、今も他のあらゆる実装が比較される基準である。