-2
$\begingroup$

How many multiplications/additions does it take to execute an FFT operation in terms of the length of the signal $N$ and the number of FFT bins $M$? I don't want an answer in terms of big O, but rather in terms of just $N$ and $M$.

$\endgroup$
  • $\begingroup$ Well, FFT is just a class of methods: What are you expecting? And, frankly, there's no difference between N and M – an FFT always transforms an N-element vector. $\endgroup$ – Marcus Müller Jan 15 '18 at 22:29
  • 1
    $\begingroup$ maybe it would help if you could explain why you (think) you need this number – while the O() notation is useful to give one a feeling of the order of complexity, absolute numbers are largely meaningless, because on real CPUs, memory bandwidth is usually the dominating factor for large transforms, and setup / data copying for small; in hardware, the numbers are hardly helpful, because depending on your use case, you'd multiplex, iteratively or fully parallely implement an FFT. $\endgroup$ – Marcus Müller Jan 15 '18 at 22:40
1
$\begingroup$

If you are interested in more involved numbers of operations, you can check A modified split-radix FFT with fewer arithmetic operations, by Johnson and Frigo, IEEE Transactions on Signal Processing, 2007, authors of the "Fastest Fourier Transform in the West" (FFTW). For instance, they claims that the classic radix-2 is about

$$ 5N\log_2 N$$

while the split-radix yields:

$$4N \log_2 N − 6N + 8\,,$$

and they achieve the improvement:

$$\frac{34}{9} N \log_2 N − \frac{124 }{27 }N − 2 \log_2 N − \frac{2}{9} (−1)^{\log_2 N} \log_2 N + \frac{16}{27} (−1)^{\log_2 N} + 8\,.$$

As said by others, you can see this number depends on implementations.

| improve this answer | |
$\endgroup$
0
$\begingroup$

Counting the exact number of multiplications and additions rarely helps because the actual number, type and timing of instructions to execute depends on the architecture being used to implement the FFT algorithm. And as @MarcusMüller stated, memory data move operations will have a big impact on the total execution time of the algorithm in addition to the number of arithmetics.

However for the most basic case the well known approximation to the computational cost of an $N$-point radix-2 FFT of a signal of length $N$ is: $$ \frac{N}{2} \log_2(N) $$ complex MACs. Note that each complex MAC can be broken into about $4$ real MACs.

When you compute $M$-point FFT of an $N$ point signal you would set $N=M$ by either zero padding to $M$ when $N < M$ or by truncating to $M$ when $N > M$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ if you can find a way to avoid multiplication by $1$ and by $j$ (with the latter your code is designed to swap around the real and imaginary parts of whatever value is being multiplied by $j$ ), then i think the number of complex multiplies is $$ \tfrac{N}{2} \log_2 \left( \tfrac{N}{2} \right) $$ $\endgroup$ – robert bristow-johnson Mar 17 '18 at 0:16
  • $\begingroup$ @Fat32: If this question has too long an answer, don't worry about it ( I'm still reading Briggs and Henson when time allows so maybe it explains later ) but doesn't adding zeros or truncating, change the signal ? Thanks. $\endgroup$ – mark leeds Mar 17 '18 at 0:23
  • $\begingroup$ also, i think the general cost formula for a radix-$2^p$ FFT is of the form: $$ A \, N\log_2(N) \ +\ B \, N \ + \ C \, \log_2(N) \ + \ D$$ for some constants $A,B,C,D$ that will be machine dependent and algorithm dependent. usually only the first two terms you need to worry about in counting cost. $\endgroup$ – robert bristow-johnson Mar 17 '18 at 0:24
  • $\begingroup$ @Fat2: Never mind by bad question. I see now that you change the number of bins, not the signal. my apologies. $\endgroup$ – mark leeds Mar 17 '18 at 0:25
  • 1
    $\begingroup$ @Fat32: That's clear but I definitely need to understand DFT better in order to "appreciate" zero padding operation. Thanks. $\endgroup$ – mark leeds Mar 17 '18 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.