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

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top