On Wed, 21 Nov 2007, Thomas Mayer wrote:
Not really, as multiplication is one mathematical operation. 'Fast' in FFT means reducing the number of mathematical operation from O(N²) to O(N log N), where N is the number of analyzed frequencies, e.g. for 64 frequencies from (a constant factor times) 64²=4096 to (another constant factor times) 64 * log(64)~116 operations.
When computing orders, multiplication constants are ignored, so log bases don't matter. However, if you want to know the exact number of operations, you have to know that the FFT for powers-of-two needs 2*log2(64)*64 operations, which is 768.
Using the same trick of algorithm for non-powers of two, you can realise that log2 was only a special case: in general, the number of passes is the sum of the prime factors of the block size, so for size 63 you need 13*64 steps and for size 65 you need 18*64 steps, and various other numbers vary immensely. There are some other variants of FFT that are better for some of the worst cases of size, but not all of them.
And then those operations are just the complex multiplications: you also have to do complex additions, and those operations also have sub-operations.
_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal QC Canada