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