2
$\begingroup$

In section 30.2 of CLRS (third edition), they given an algorithm for computing the fast Fourier transform of a vector represented as an $n$ dimensional array when $n$ is a power of $2$. They say that an algorithm for general $n$ is beyond the scope. Is generalizing the algorithm to any $n$ very tricky? Any references where I can find generalized pseudo code that'll work for any $n$?

$\endgroup$
1
  • 1
    $\begingroup$ For prime $n$, you can't avoid $\Theta(n^2)$ operations. For composite $n$, The cost is lowered to $\Theta(n\sum_i n_i)$ where $n_i$ are the prime factors. The ideal situation is with $n=2^m$. $\endgroup$
    – user16034
    Nov 21, 2022 at 16:01

3 Answers 3

3
$\begingroup$

Notice that there is always a power of two $2^k$ between $n$ and $2n$. Thus you can extend your array of $n$ numbers to $2^k$ and fill the empty cells with zero. Because $2^k \leq 2n$ the algorithms asymptotic runtime $O(2n\log(2n)) = O(n\log(n))$ doesn't change. This is trick is commonly used in competitive programming.

$\endgroup$
3
  • $\begingroup$ Thanks! It isn't immediately obvious to me that this padding zeros won't change the output of the algorithm. Any intuitive reason why it doesn't matter? Also, very interested in the competitive programming angle. What are some problems where this trick is used? $\endgroup$ Nov 20, 2022 at 18:41
  • $\begingroup$ I wasn't clear about that: the output isn't the same. Instead of decomposing a signal of $n$ elements into $n$ "waves", we have decomposed it into $2^k$ "waves", this still useful for the application I was thinking of namely polynomial multiplication. Here you can find the code using this type of FFT too multiply two polynomials and much more. Competitive programming problems are all the way at the bottom. $\endgroup$
    – plshelp
    Nov 20, 2022 at 19:02
  • 1
    $\begingroup$ @RohitPandey in fact it does change the output of the algorithm, sometimes drastically, so this answer is wrong. Consider a 1025-sample sine wave. An FFT with n=1025 will give a single peak. An FFT with n=2048 and padding will give a quite ugly spectrum full of harmonics because adding the padding makes the signal into a completely different one. $\endgroup$
    – user253751
    Nov 21, 2022 at 11:18
3
$\begingroup$

As plshelp said, sometimes a 2^k point FFT is useful even when you want an n point Fourier transform with n < 2^k. A 1024 point FFT is not the same as a 1023 point Fourier transform, but in many situations it is useful.

You can do Fourier transformations for any n, just following the definitions, in O(n^2). If you can write n as a product, say 1000 = 2 * 2 * 2 * 5 * 5 * 5, then you can calculate the Fourier transformation quicker; I think O (n * (sum of factors)) is possible, if n = 2^k then this is O (n log n). For the case n = 2^k this is called "Fast Fourier transform" but you can do a faster than normal Fourier transformation whenever the largest prime factor of n is much smaller than n.

If n = 3 * 2^k, you can calculate that transform quite fast. Very likely faster than FFT for n = 4 * 2^k, but a bit more complicated. Or for n = 1025, you could do a transformation for n = 5 * 256 = 1280 instead of FFT for n = 2048.

$\endgroup$
1
  • $\begingroup$ Thanks. So a better than O(n^2) general algo doesnt exist? And do you have references for the algos for n=3*2^5 and such? $\endgroup$ Nov 22, 2022 at 2:45
0
$\begingroup$

Use Bluestein's FFT Algorithm, some realizations already exist. Keep in mind that this also increases the calculation error at large sizes (>10000).

$\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.