One can do better than the Cooley-Tukey FFT if the input is real-valued, which is often the case in applications. Edson modified the original algorithm to get rid of the redundancies in the calculations. To wit:
Code: PROGRAM:FFTRE
:dim(L₁)→L
:1→J
:For(I,1,L-1) \\ bit-reversal permutation
:If J>I:Then
:L₁(J)→T
:L₁(I)→L₁(J)
:T→L₁(I)
:End
:L/2→K
:While K<J
:J-K→J:K/2→K
:End
:J+K→J
:End
:DelVar H:1→M \\ main FFT routine
:While M<L
:H→Q:M→H:2M→M
:For(I,1,L,M)
:I+H→K
:L₁(I)→U
:L₁(K)→V
:U+V→L₁(I)
:U-V→L₁(K)
:If Q:Then
:K+Q→K
:-L₁(K)→L₁(K)
:End:End
:π^r/H→θ \\ ^r - radian sign
:For(J,1,Q-1)
:cos(Jθ)→C
:sin(Jθ)→S
:For(I,1,L,M)
:I+J→R:I-J+H→T
:L₁(R+H)→V
:L₁(T+H)→W
:CV+SW→U
:CW-SV→V
:L₁(T)→W
:V+W→L₁(T+H)
:V-W→L₁(R+H)
:L₁(R)→W
:W-U→L₁(T)
:W+U→L₁(R)
:End:End:End
:L₁
As with FFTCT, FFTRE can only handle list lengths that are powers of two. The output is in the so-called "conjugate even" format. Unfortunately, FFTRE has no support for the A and B parameters as in FFT and FFTCT. Here is an example of how it's used, and a comparison with FFTCT (output rounded to five significant digits after the decimal point):
Code:
e^(-seq(X,X,0,15)/8)→L₁:prgmFFTRE
{7.35865, 1.0778, 0.61251, 0.519005, 0.486094, 0.471298, 0.463927, 0.460381, 0.459318, -0.085648, -0.178261, -0.28725, -0.428977, -0.638934, -1.01659, -1.97093}
e^(-seq(X,X,0,15)/8)→L₁:1→A:-1→B:prgmFFTCT
{7.35865, 1.0778-1.97093i, 0.61251-1.01659i, 0.519005-0.638934i, 0.486094-0.428977i, 0.471298-0.28725i, 0.463927-0.178261i, 0.460381-0.085648i, 0.459318, 0.460381+0.085648i, 0.463927+0.178261i, 0.471298+0.28725i, 0.486094+0.428977i, 0.519005+0.638934i, 0.61251+1.01659i, 1.0778+1.97093i}
To explain the "conjugate even" format a bit, note that for the length-16 list L₁, the first and ninth (16/2+1) list elements are real and identical in both outputs. For the second element of FFTCT's output, its real part is the second element of FFTRE's output, and its imaginary part is the 16th element of FFTRE's output (correspondingly, the 16th element of FFTCT's output holds the conjugate of the second element). The redundancy inherent in FFTCT's output is eliminated in FFTRE; instead of two list elements holding a complex number and its conjugate, the two elements hold two real numbers corresponding to the real and imaginary parts. There is a similar correspondence between the other complex elements of FFTCT and the elements of FFTRE.
The algorithm is adapted from this paper.
thornahawk |