From the algorithm complexity point of view It is well-known that a radix-4 FFT is better than a radix-2 FFT, a radix-8 FFT is better than a radix-4, and a radix-16 is better than a radix-8 FFT algorithm.
Has anyone tried out and measured the final execution times after rearranging the output data in its initial order? Is radix-2 really better than radix-4 and if so, how much better it is?
Radix-2 saves multiplications for factors differing by pi by incorporating them in the algorithm as addition and subtraction. Radix-4 saves multiplications for factors differing by pi/2 by incorporating them as multiplying by 1, i, -1 and -i. Radix 4 is faster than radix-2, but for radix-4 N has to be a power of 4 while for radix-2 N has to be a power of 2.
The issue is what do you lose when you extend your dataset to be a power of 2 or 4 or whatever (and how to guarantee that the results do not depend too much on the extra values you provide to do so, or at least measure how much they do) - this is true much more generally: specializations can be made more efficient, at the cost of not applying as widely or of requiring extraneous conditions to fit the specialized requirements
@Christopher Landauer - No the issue is not that you have to extend the number of samples. The issue is that the radix-4 algorithm itself incorporates the multiplications by 1, i, -1 and -i saving time.
As Peter said, this depends on your target processor. A specialised DSP with reverse carry buffers, enhanced Arithmetic Logic Unit (ALU) and Address Generation Unit (AGU) who is able to perform one mac-computation and two move-commands in one instruction cycle can handle the radix-2 butterfly algorithm very efficiently.
E.g. for a Motorola DSP driven by 150MHz the family manual states that the N-Radix-2 DIT algorithm needs 8N+9 instructions.
(Page 451, http://tinyurl.com/loyksbp )
A 1024 FFT on the 150MHz DSP will execute in (1/150MHz) * (8 *1024 +9) = 55µs.
With the highest precision!
So, for me it`s not only interesting, how fast are these algorithms in comparison but at which costs of accuracy I`ll gain more speed on execution.
Doing e.g. time measurements in range of picoseconds the accuracy of the calculations is more important.
Best regards,
Marc
- Badges
- Science topic