Yes, that is correct. In hindsight, I should have done a better job at making
this more explicit.
The key point is that w needs to be a principal nth root of unity, where n is
the length of the powerlist. But in a recursive call, the length of the
powerlist is equal to n/2. But w is a principal nth root of unity; what we
really need is an (n/2)th root of unity.
By the Cancellation Lemma, which we never really stated in the lecture or the
project, if w is an nth root of unity, then w^2 is an (n/2)th root of unity.
Therefore, changing w to w^2 in a recursive call to FFT or IFT will produce the
correct result.
David
Clearly you do not understand the project specification. It blatanly states
that w changes to w^2 after an iteration of FFT. I think you failed to look
over it closely enough. Please exhaust all your options before posting on the
newsgroup.