高速フーリエ変換のプログラム中、どの符号が逆転するかを一々分岐させると、分岐の判定に時間がかかり、パフォーマンスが落ちる。一方、正変換のプログラムと、逆変換のプログラムを両方用意しておくことも考えられるが、共通部分が多いため、無駄が多くなる。このため、複素共役を使った次のような方法が考えられる。離散フーリエ変換をで定義したとき、逆変換はとなる。このため、の離散フーリエ逆変換を求めるには、とすれば良く、正変換の高速フーリエ変換のプログラムがあれば、逆変換は容易に作ることができる。アルゴリズム.分割統治法を使ったアルゴリズムで、のサイズの変換を、より小さいサイズである,のサイズの変換に分割していくことで高速化を図っている。伝統的なFFTの処理実装の多くは、再帰的な処理を、系統だった再帰をしないアルゴリズムにより実現している。原理の簡単な説明.となる。入力列を添字の偶奇で分けて、以下のように変形する。すると、サイズのFFTの演算結果を用いて表現でき、サイズの分割ができる。また、この分割手順を図にすると蝶のような図になることから、バタフライ演算とも呼ばれる。原理の説明.とする。次離散フーリエ変換を、以下のように次離散フーリエ変換と次離散フーリエ変換に分解する。次離散フーリエ変換:を、について計算することを考える。,を次のように書き換える。ただしまたである。するとここで、と置くと、ステップ1、2は、次の離散フーリエ変換を、次の離散フーリエ変換と回転因子の掛け算の実行により、組()の次離散フーリエ変換に分解したと見ることができる。このため、の累乗あるいはの累乗次の離散フーリエ変換は簡単に計算できる。実務的に用いられるのは、かの場合のみである。なお、かの場合のこの部分の次の離散フーリエ変換のことを、バタフライ演算と言う。ビットの反転.一方、となる。繰り替えせば、となるが、左辺についてより,また右辺についてより。このため、プログラムの例.'フーリエ変換'回転因子'ビット反転実数および対称的な入力への最適化.多くの応用において、FFTに対する入力データは実数の列(実入力)であり、このとき変換された出力の列は次の対称性を満たす(は複素共役):