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

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.

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!

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

polynomialspadded with zeroes themselves. It doesn't matter if you multiply 3 +x+ 4x^{2}with 7 + 2x, or 3 +x+ 4x^{2}+ 0x^{3}with 7 + 2x+ 0x^{2}+ 0x^{3}. Therefore you can always assume that the input polynomials have 2^{k}coefficients. The intermediate transformswillbe 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

reallyneed 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.That's quite interesting.

Thank you!

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 [

a_{0},a_{1}, ...,a_{n - 1}] is to first find the corresponding polynomialP(x) =a_{0}+a_{1}x+a_{2}x^{2}+ ... +a_{n - 1}x^{n - 1}. If we denote the FFT of the array [a_{0},a_{1}, ...,a_{n - 1}] as [b_{0},b_{1}, ...,b_{n - 1}], thenb_{j}is defined as . The FFT is simply an evaluation of the polynomial inndifferent points! Nothing here has to do withnbeing 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

nhas 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

nis not a power of two, and it cannot be fixed by just padding with zeros as there is anndependence in .So what if

nis 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 arbitraryn.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 ifnis 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.

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