2
$\begingroup$

Given a signal of length $N = P^m$, $P$ prime, what is a reasonable upper bound on the number of operations (complex additions and multiplications) needed to compute the Fast Fourier Transform (FFT) of this signal?

I have been able to show that the number of operations needed is at most $(5P/2 - 2) N \log_P N$, but there is one weak step in my proof. I am confident in the validity of this step (finding a simple upper bound for a more complicated function), but I do not have a rigorous proof of it. I'm curious to see what other upper bounds are known, and if they have better proofs than mine (hopefully they do!).

$\endgroup$
2
$\begingroup$

The Cooley-Tukey algorithm achieves n/2 log2(n/2) complex multiplications and n log2(n) complex additions in the case p=2. It's my understanding that one can obtain (p-1) n logp(n) complex multiplications for general p, but I don't know how many additions nor a good reference.

The best known number of real multiplications and additions is about 34/9 n log2(n) in the case p=2 again, which is of course within a small factor of the number of complex multiplications and additions.

One should also note that there are algorithms (like the z-transform) that obtain O(n log n) arithmetic operations regardless of the prime factorization of the input size. As such, this will eventually be smaller than your expression.

$\endgroup$
1
  • $\begingroup$ Z-transform isn't an algorithm but rather a function... maybe you meant Chirp-Z transform? $\endgroup$
    – user541686
    Mar 14 '19 at 23:32

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.