高速フーリエ変換
ここで、
f 1 ( p , r ) = exp  ( − 2 π i p r P Q ) ∑ q = 0 Q − 1 f ( q P + p ) exp  ( − 2 π i r q Q ) {\displaystyle f_{1}(p,r)=\exp \left(-2\pi i{\frac {pr}{PQ}}\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)}
と置くと、
F ( n ) = F ( s Q + r ) = ∑ p = 0 P − 1 exp  ( − 2 π i s p P ) f 1 ( p , r ) {\displaystyle F(n)=F(sQ+r)=\sum _{p=0}^{P-1}\exp \left(-2\pi i{\frac {sp}{P}}\right)f_{1}(p,r)}
となる。即ち、F(n) = F(sQ + r) の計算は、次の2ステップになる。
, r 2 , r 1 ) {\displaystyle F(s_{k}Q^{k}+r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1})=\sum _{p_{k}=0}^{Q^{k-k}-1}\exp \left(-2\pi i{\frac {s_{k}p_{k}}{Q^{k-k}}}\right)f_{k}(p_{k},r_{k},r_{k-1},\dots ,r_{2},r_{1})}
となるが、左辺について
s k Q k + r k Q k − 1 + ⋯ + r 2 Q + r 1 < Q k {\displaystyle s_{k}Q^{k}+r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1}<Q^{k}}
より sk = 0, また右辺について
Q k − k − 1 = 0 {\displaystyle Q^{k-k}-1=0}
より pk = 0。このため、
F ( r k Q k − 1 + ⋯ + r 2 Q + r 1 ) = f k ( 0 , r k , r k − 1 , ... , r 2 , r 1 ) . {\displaystyle F(r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1})=f_{k}(0,r_{k},r_{k-1},\dots ,r_{2},r_{1}).}
これは f ( r 1 Q k − 1 + r 2 Q k − 2 + ⋯ + r k − 1 Q + r k ) {\displaystyle f(r_{1}Q^{k-1}+r_{2}Q^{k-2}+\cdots +r_{k-1}Q+r_{k})} のあった場所に格納されている。
F ( n ) = F ( s Q + r ) = ∑ p = 0 P − 1 ∑ q = 0 Q − 1 f ( q P + p ) exp  ( − 2 π i ( q P + p ) ( s Q + r ) P Q ) = ∑ p = 0 P − 1 ∑ q = 0 Q − 1 f ( q P + p ) exp  ( − 2 π i ( r q Q + s p P + p r P Q ) ) = ∑ p = 0 P − 1 [ exp  ( − 2 π i ( s p P + p r P Q ) ) ∑ q = 0 Q − 1 f ( q P + p ) exp  ( − 2 π i r q Q ) ] {\displaystyle {\begin{aligned}F(n)&=F(sQ+r)=\sum _{p=0}^{P-1}\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {(qP+p)(sQ+r)}{PQ}}\right)\\&=\sum _{p=0}^{P-1}\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i\left({\frac {rq}{Q}}+{\frac {sp}{P}}+{\frac {pr}{PQ}}\right)\right)\\&=\sum _{p=0}^{P-1}\left[\exp \left(-2\pi i\left({\frac {sp}{P}}+{\frac {pr}{PQ}}\right)\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)\right]\end{aligned}}}