Nooor's blog

FFT on Array Whose Size is not a Power of Two
By Nooor, history, 6 years ago, In English

Hello Codrforces,

I don't have a quite strong grisp of FFT, although I have a question, what if I wanted to apply FFT on an array whose size is not a power of two, pretty much every implementation I've seen on the interent assumes the length of the input array is a power of two, would it be possible to pad the array with zeros?

I'm wondering what the right approach would be? Thank you all

Tags fft
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes,adding 0s at the end is the usual approach.This way,you'll keep the complexity (the size of the array increases less than twice),and the algorithm would work the same.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thank you, but out of curiosity I tried to pad an array with zeros and run the FFT on the actual array in Matlab and run my FFT code on the padded array and the results weren't identical, though when the array size is a power of two the results are identical, I guess Matlab does something else then!

    → Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

TL;DR: in 99% of the cases, you can safely pad the array with zeroes.

Agreed, the discrete Fourier transform of some array of length 7 is totally different from the transform of this array padded to length 8. However, in competitive programming, it usually doesn't matter.

It all depends on what you want to achieve with FFT:

  • If it's some polynomial multiplication (or similar stuff), you can imagine the polynomials padded with zeroes themselves. It doesn't matter if you multiply 3 + x + 4x2 with 7 + 2x, or 3 + x + 4x2 + 0x3 with 7 + 2x + 0x2 + 0x3. Therefore you can always assume that the input polynomials have 2k coefficients. The intermediate transforms will be different for different transform sizes, but the result of the multiplication will remain the same.

  • If you need to do some signal processing, you probably can choose the transform sizes equal to the powers of two.

  • If you really need an efficient transform for sizes other than powers of two (which is rarely needed), you may use the Bluestein's algorithm. It's a bit complicated, though.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    That's quite interesting.

    Thank you!

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Here is the thing, the definition of FFT does not in any way include a power of two.

I think that the easiest way to understand FFT of a an array [a0, a1, ..., an - 1] is to first find the corresponding polynomial P(x) = a0 + a1x + a2x2 + ... + an - 1xn - 1. If we denote the FFT of the array [a0, a1, ..., an - 1] as [b0, b1, ..., bn - 1], then bj is defined as . The FFT is simply an evaluation of the polynomial in n different points! Nothing here has to do with n being a power of two.

So where does the power of two come in? It comes from the divide and conquer used to quickly calculate the transform, see Cooley-Tukey FFT algorithm. It uses the fact that the FFT of the odd coefficients and the even coefficients can be calculated separately and then be combined to find the total FFT, a bit similar to how merge sort works. But because of how this divide and conquer algorithm works at each step n has to be divisible by two.

The reason why everyone wants to use Cooley-Tukey's is because it is very quick and also very simple to implement. It does not however work if n is not a power of two, and it cannot be fixed by just padding with zeros as there is an n dependence in .

So what if n is not a power of two? There is actually a way to do padding to powers of two called Bluestein's algorithm. It calls Cooley-Tukey multiple times so it is quite a bit slower than standard Cooley-Tukey. Still it is relatively easy to implement so this is probably the way I would implement FFT so that it works for arbitrary n.

Another way is to use a generalization of Cooley-Tukey that allows for divide and conquer of any size that divides n, this is mostly only useful if n is divisible by some small prime factor. I wouldn't implement this myself because if I need the speed I would just use other peoples implementations, see FFTW or FFTS.

If you want to learn more about FFT I suggest reading these lecture notes.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    That's a great answer, thank you@

    BTW, I've been reading up about the topic and played around with the FFTW lib, it's fantastic :D

    → Reply