高速フーリエ変換
395--397、の中では Danielson and Lanczos(1942年)などの先行例をあげている。和書でも沼倉三郎:「測定値計算法」、森北出版、(1956年)には,一般の合成数Nに対してではないが人が計算を行う場合にある程度の大きさの合成数Nに対してどのように計算すればよいかについての説明をみることができる)。 以下の書籍にも、天体観測の軌道の補間のためにガウスが高速フーリエ変換を利用したことが書かれている。
Elena Prestini:"The Evolution of Applied Harmonic Analysis", Springer, ISBN 978-0-8176-4125-2 (2004)のSec.3.10 'Gauss and the asteroids: history of the FFT'.
( ∵ W k + N = W k {\displaystyle \because W^{k+N}=W^{k}} )
すると、サイズ 2 のFFTの演算結果を用いて表現でき、サイズの分割ができる。
[ X 0 X 1 X 2 X 3 ] = [ 1 0 W 0 0 0 1 0 W 1 1 0 W 2 0 0 1 0 W 3 ] [ W 2 0 W 2 0 0 0 W 2 0 W 2 1 0 0 0 0 W 2 0 W 2 0 0 0 W 2 0 W 2 1 ] [ x 0 x 2 x 1 x 3 ] {\displaystyle {\begin{bmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{bmatrix}}={\begin{bmatrix}1&0&W^{0}&0\\0&1&0&W^{1}\\1&0&W^{2}&0\\0&1&0&W^{3}\end{bmatrix}}\,{\begin{bmatrix}W_{2}^{0}&W_{2}^{0}&0&0\\W_{2}^{0}&W_{2}^{1}&0&0\\0&0&W_{2}^{0}&W_{2}^{0}\\0&0&W_{2}^{0}&W_{2}^{1}\end{bmatrix}}\,{\begin{bmatrix}x_{0}\\x_{2}\\x_{1}\\x_{3}\end{bmatrix}}}
また、この分割手順を図にすると蝶のような図になることから、バタフライ演算とも呼ばれる。
バタフライ演算は、計算機上ではビット反転で実現される。DSPの中には、このバタフライ演算のプログラムを容易にするため、ビット反転アドレッシングを備えているものがある。