n = a.length
if n == 1
return a
ωn = e2πi/n
ω = 1
a[0] = (a0, a2, ..., an - 2)
a[1] = (a1, a3, ..., an - 1)
y[0] = Recursive-FFT(a[0])
y[1] = Recursive-FFT(a[1])
for k = 0 to n/2 - 1
yk = yk[0] + ωyk[1]
yk+(n/2) = yk[0] - ωyk[1]
ω = ωωn
return y
|
n = y.length
if n == 1
return y
ωn = 1 / e2πi/n
ω = 1
y[0] = (y0, y2, ..., yn - 2)
y[1] = (y1, y3, ..., yn - 1)
a[0] = Inverse-FFT(y[0])
a[1] = Inverse-FFT(y[1])
for k = 0 to n/2 - 1
ak = ak[0] + ωak[1]
ak+(n/2) = ak[0] - ωak[1]
ω = ωωn
for k = 0 to n - 1
ak = ak / n
return a
|