1
$\begingroup$

Calculate the amount of operations you need for the Fast Fourier Transform.

Take $N=2048 \times 2048$

$N\dfrac{\log(N)}{\log(2)}$

$\dfrac{\log(2048 \times 2048)}{\log(2)}$ is 22.

$(2048 \times 2048) \dfrac{\log(2048 \times 2048)}{\log(2)}$ is 92274688.

But does $92274688$ stand for total operations or $92274688$ adds AND $92274688$ multiiplications?

So the total amount of operations is $2\times 92274688=184549376$.

$\endgroup$

migrated from math.stackexchange.com May 23 '13 at 18:08

This question came from our site for people studying math at any level and professionals in related fields.

  • $\begingroup$ I suppose to get a 2D FFT. width is 1920 and height is 1080. Why can't I use this for a 2D FFT? I remember that not all FFTs require a N with a power of 2. Are you sure I'm wrong? $\endgroup$ – user8005 May 23 '13 at 14:23
  • $\begingroup$ Deleted my comments. I'm going to submit an answer with some clarification. $\endgroup$ – Michael Grant May 23 '13 at 14:56
  • $\begingroup$ This integer sequence in the oeis might be relevant: oeis.org/A059975 "n*a(n) is the number of complex multiplications needed for the fast Fourier transform of n numbers" $\endgroup$ – Mats Granvik May 23 '13 at 15:39
  • $\begingroup$ I read that FFTW supports combinations of powers of small primes (2, 3, 5, 7). 1080 = $1920 = 2^7 \cdot 3 \cdot 5$ $2^3 \cdot 3^3 \cdot 5$. I read that FFTW should be able to process these without any padding for 1920*1080. $\endgroup$ – user8005 May 23 '13 at 17:51
  • 1
    $\begingroup$ Indeed it can, but of course the cost isn't an easy formula based on $\log_2$ anymore. $\endgroup$ – Michael Grant May 23 '13 at 20:47
4
$\begingroup$

{EDIT: The original question concerned a $1920\times 1080$ FFT, not a $2040\times 2048$ FFT. So the parts of this answer that deal with sizes that are not powers of two are no longer relevant. I will leave them anyway. The last part of this answer, dealing with complex vs. real operations, remains relevant.}

A 2-D FFT of size $N_1\times N_2$ is equivalent to performing $N_1$ FFTs of size $N_2$, and $N_2$ FFTs of size $N_1$. So the cost becomes $$C_{2D}(N_1,N_2) = N_1C_{1D}(N_2)+N_2C_{1D}(N_1),$$ where $C_{1D}(N)$ is the cost of a single $N$-point, 1-D FFT. Your proposed calculations are correct, then, if you assume $C_{1D}(N)=2N\log_2 N$, because this evaluates to $$2N_1N_2(\log_2 N_1+\log_2 N_2)=2N_1N_2\log_2(N_1N_2).$$

[EDIT: This paragraph is no longer relevant; the OP has changed the FFT sizes to a power of two.] However, your other problem is that $C(N)$ is not necessarily $kN\log_2 N$ (or close to it) unless $N$ is a power of two. In particular, if $N$ is prime, then you're going to need $kN^2$ operations. For values of $N$ that are composite prime factors, then the computational complexity is a function of the number of prime factors and their values. See this page for a discussion of efficient prime factor FFTs. Roughly speaking, if the number of prime factors is sufficiently large, then the cost is going to grow like $N\log N$.

Even for powers of two, $C_{1D}(N)=2N\log_2 N$ is not quite right for several reasons. First of all, the standard radix-2 FFT actually requires $(N/2)\log_2 N$ complex multiplications and $N\log_2 N$ complex additions. Furthermore, you really don't want to just add these two counts together. After all, one complex addition requires 2 real additions, and one complex multiplication requires 4 multiplications and 2 additions. So if you want to combine these two operation counts, you need to do it in terms of these real operations, giving you $C_{1D}=5N\log_2 N$ real operations.

You can do significantly better than this, it turns out, if you take a careful accounting of "trivial" complex multiplications. One of the most efficient algorithms from a real operation standpoint is the split-radix algorithm (which requires a power of two) requires $C_{1D}(N)=4N\log_2 N-6N+8$ real multiplications and additions for a single FFT. For a 2-D FFT of size $N_1\times N_2$, the total cost would be $$\begin{aligned} C_{2D}(N_1,N_2)&=N_1(4N_2\log_2 N_2-6N_2+8)+N_2(4N_1\log_2 N_1-6N_1+8)\\ &=4N_1N_2\log_2(N_1N_2)-12N_1N_2+8(N_1+N_2). \end{aligned}$$

Finally, let me add that counting floating point operations is a crude way to measure practical performance. Memory access patterns are often a more important factor in performance. Quoting Wikipedia: "In practice, actual performance on modern computers is usually dominated by factors other than the speed of arithmetic operations and the analysis is a complicated subject (see, e.g., Frigo & Johnson, 2005), but the overall improvement from O(N2) to O(N log N) remains."

$\endgroup$
  • 1
    $\begingroup$ Oh I see, you have updated the question to 2048 x 2048. Then yes, some of my answer no longer applies---the parts that refer to non-powers of two. But the rest does. $\endgroup$ – Michael Grant May 23 '13 at 15:41
  • 1
    $\begingroup$ I do not agree. I agree that it is $O(MN\log MN)$ however. In other words, it's correct to within a multiplicative constant, if you ignore lower-order terms. $\endgroup$ – Michael Grant May 23 '13 at 15:47
  • 1
    $\begingroup$ No. See the text: "Even for powers of two..." and onwards. $\endgroup$ – Michael Grant May 23 '13 at 16:00
  • 1
    $\begingroup$ Right. But with modern processors that is not likely to be a win, especially if there are fused multiply-adds. And it comes at a cost of reduced precision. $\endgroup$ – Michael Grant May 23 '13 at 20:46
  • 1
    $\begingroup$ Please read a text on how floating-point arithmetic is performed. ANY TEXT. Then you will understand that the same circuit performs addition and subtraction. That's why you never see subtraction mentioned in floating point operation counts. This will be the last time I comment. $\endgroup$ – Michael Grant May 23 '13 at 22:06

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.