4基底周波数間引き高速フーリエ変換(疑似コード)
Radix4FFT(𝐚,start,end)
N = start-end
if(N==2)
s = start //下付きにするため
temp = aₛ+aₛ₊₁
aₛ₊₁ = aₛ - aₛ₊₁
aₛ = temp
else
n = (start-end)/4
for x from 0 to n-1
for j from 0 to 1
l = j*n
m = l+2*n
temp = aₓ₊ₗ+aₓ₊ₘ
aₓ₊ₘ = (aₓ₊ₗ-aₓ₊ₘ)*i //実数部と虚数部の交換と符号反転
aₓ₊ₗ = temp
for j from 0 to 1
l = j*2*n
m = l+n
if(j==0)
temp = aₓ₊ₗ+aₓ₊ₘ
aₓ₊ₘ = (aₓ₊ₗ-aₓ₊ₘ)*exp(-i2π2x/N)
else
temp = (aₓ₊ₗ+aₓ₊ₘ)*exp(-i2πx/N)
aₓ₊ₘ = (aₓ₊ₗ-aₓ₊ₘ)*exp(-i2π3x/N)
aₓ₊ₗ = temp
Radix4FFT(𝐚,start,start+n)
Radix4FFT(𝐚,start+n,start+2n)
Radix4FFT(𝐚,start+2n,start+3n)
Radix4FFT(𝐚,start+3n,end)