[PD] fft beginner question

Mathieu Bouchard matju at artengine.ca
Thu Nov 22 02:25:34 CET 2007

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 

  _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - tél:+1.514.383.3801, Montréal QC Canada

More information about the Pd-list mailing list