复数

众所周知,由于做快速傅里叶变换时,要先将两个多项式 f(x),g(x)f(x),g(x) 分别DFT,点值相乘后再IDFT,其常数是巨大的。但如果其系数均为实数,我们就可以通过构造多项式的方式,充分利用复数虚部存储需要的信息。下文中默认有 deg(f(x))=deg(g(x))=n=2s\operatorname{deg}(f(x))=\operatorname{deg}(g(x))=n=2^s。记 nn 次单位根为 ωn\omega_{n}

考虑构造两多项式 p(x)=f(x)+ig(x),q(x)=f(x)ig(x)p(x)=f(x)+\mathrm{i}g(x),q(x)=f(x)-\mathrm{i}g(x),则假若我们求出 p(x)p(x) 的点值表示,就会有 p(ωnk)=q(ωnk modn)\overline{p(\omega_n^k)}=q(\omega_n^{-k\space\bmod n})(更多…)

More
  • 2022年7月3日