# [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
sub-operations.

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