Possible new faster algorithms for FFT of 3^n and 6^n sizes.
in [DSP]
|
From: sfuerst on 5 Jan 2010 23:37 Hello, I think I may have discovered new faster algorithms for doing FFTs on vectors of length 3^n and 6^n. Complete source code plus a derivation may be found at: http://locklessinc.com/articles/non_power_of_2_fft/ Basically, the trick is to use the first sixth root of unity as a complex axis instead of the imaginary number i. Converting into this form takes O(3n) operations, as does converting back. The advantage is that multiplying numbers by third or sixth roots of unity in this form becomes trivial. The result is that large numbers of operations can be removed for FFTs of radix 3 or 6 provided you stay in the altered number system. The result is that 3^n takes ~ 5.47n lg(n) floating point operations, and 6^n takes 4.51n lg(n). The radix 6 FFT can be improved further by converting to a split-radix method. The best I found was a 1/2,1/6,1/6,1/6 split. The resulting algorithm asymptotically takes 4.09n lg(n) flops. This is only about 2% slower than the radix 2/4 split radix method. Of course, the fastest known FFT method improves the 2/4 split radix method further via using the tangent trick. However, I couldn't find an easy way to do this for radix six. Steven
|
Pages: 1 Prev: extended kalman filter going berserk Next: Interpolation response overshoot, why? |