Fast Fourier transform for a sequence of complex numbers with arbitrary size

75 Views Asked by At

I want to apply fast Fourier transform for a sequence of complex numbers with length N. N can be anything (not necessarily a power of 2). It seems that Cooley–Tukey algorithm only works for the sequences with length of a power of 2. I was wondering whether exists other algorithms with time complexity of $O(NlogN)$ which works with no restrictions on N? Thank you in advance for your help.