Discrete fourier transform of a polynomial whose degree is not a power of 2

Question

I need to evaluate a polynomial of degree n at the n cube roots of unity. Simple evaluation would take $O(n^2)$ time. I know that polynomial evaluation can be done in $O(n\log n)$ time using FFT.

But the problem that I am facing is this. FFT only works when $n$ is a power of 2. If I extend my polynomial by appending zeroes at the end, that would not solve my problem because then I would be evaluating my polynomial at cube roots of $m$ (where $m$ is a power of $2$ greater than $n$) which I don't want.

Any ideas on this?

Answer 1

There are FFT algorithms for prime sizes such as Rader's algorithm. Given a factorization of $n$ as a product of (not necessarily different) primes, you can compute the DFT by running Rader's algorithm for each prime, in the same way that the usual FFT works by in effect computing FFTs of size $2$. You can read the details in a paper by Frigo and Johnson which describes the FFTW library, which computes length $n$ DFTs in $O(n\log n)$ for all $n$. You can also just use the library if all you really need to do is compute FFTs (rather than solve some programming exercise in some course).