OI FFT“三次转两次”优化 众所周知,由于做快速傅里叶变换时,要先将两个多项式 f(x),g(x)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^sdeg(f(x))=deg(g(x))=n=2s。记 nnn 次单位根为 ωn\omega_{n}ω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)=f(x)+ig(x),q(x)=f(x)−ig(x),则假若我们求出 p(x)p(x)p(x) 的点值表示,就会有 p(ωnk)‾=q(ωn−k mod n)\overline{p(\omega_n^k)}=q(\omega_n^{-k\space\bmod n})p(ωnk)=q(ωn−k modn)。 (更多…) More 2022年7月3日