3
$\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$
2
  • $\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$ Commented Jan 15, 2018 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$ Commented Jan 15, 2018 at 22:40

1 Answer 1

3
$\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 claim that the complexity of the classic radix-2 is about:

$$ 5N\log_2 N$$

while the split-radix yields:

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

and they achieved 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, and that the actual gain is subtle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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