快速傅立叶变换 - 乘法多项式？

Question

我只是不明白如何对两个多项式执行FFT,例如X ^ 2 + 1和X + 1 ......任何人都可以一步一步地与我一起完成这个过程吗？

非常感谢

Answer 1

只需使用多项式系数作为fft的输入:

octave:16> poly1=[1 0 1 0]
poly1 =

   1   0   1   0

注意:这意味着x ^ 2 + 1

octave:17> poly2=[1 1 0 0]
poly2 =

   1   1   0   0

octave:18> ifft( fft(poly1).*fft(poly2))
ans =

   1   1   1   1

这是结果.解释为x ^ 3 + x ^ 2 + x + 1,这是两个多项式的乘积.