When you recursively split into $Y_{even}$ and $Y_{odd}$, from the second recursion onwards don't these sets have their even-ness and odd-ness violated? I.e., assume you are running the FFT algorithm on the first $Y_{even}$ (first time hitting step 5 below). The new $Y_{odd}$ in this recursive branch is made entirely of even terms. How does that not break the validity of $x*Y_{odd}$ being even, and thus the -f(x) giving you values for f(-x)?

My understanding was that this was a key assumption for that particular efficiency in the algorithm.

As a follow-on question: why do we need to pick roots of unity to build points from? I.e. why does using numbers which aren't the relevant roots of unity as x coordinates break the algorithm?

The algorithm I'm using is printed below for clarity:

FFT for polynomial multiplication


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.