Expected Behavior of FFT
-
04-11-2019 - |
Question
I am debugging an FFT. My FFT uses complex numbers in polar form, $(r,\theta)$.
I am trying to establish that it works, with a unit test. My real values are all correct, after a polynomial multiplication...
However, I pad out my polynomials to a power of two with complex zeros, and when the multiplication is complete, I have random angle values in the polar form of the complex numbers.
For instance, I multiply the following polynomials, listed in standard form by their coefficients:
$$ A = \lbrace1,2,3\rbrace\\ B = \lbrace4,5,6\rbrace\\ $$
And I am expecting the answer to be: $$ C = \lbrace (4,0),(13,0),(28,0),(27,0),(18,0),(0,0),(0,0),(0,0)\rbrace $$
However, my FFT returns this exactly (ignoring floating point errors), except the last three terms are:
$$ C = \lbrace \ldots,(0,4.518),(0,0.4769),(0,2.2877)\rbrace $$
My question is whether these angle values in the extra terms are expected, or whether this is a sign of something going wrong in my FFT code?
(this is tricky for me, because it seems like everything is calculating correctly; and shouldn't it not work at all in a d&c if something is wrong?)
No correct solution