0
$\begingroup$

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

$\endgroup$

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.