「学习笔记」Bluestein's FFT Algorithm 任意长度卷积算法
简略介绍Bluestein’s FFT Algorithm，一种用于计算任意长度卷积的算法。
适用范围
简而言之，仅适用于存在单位根的情况
- 显然FFT可以，\(\omega_n=e^{\frac{2\pi i}{n}}\)
- NTT需满足\(n\mid (Mod - 1),\omega_n=g^\frac{Mod-1}{n}\)
推式子
考虑DFT的实质：求单位根处的点值。
设\(f(x)=\sum\limits^n_{i=0}a_ix^i\)
\(f(\omega_n^k)=\sum\limits^n_{i=0}a_i\omega_n^{ik}\)
考虑\(ik=\binom{i+k}{2}-\binom{i}{2}-\binom{k}{2}\)（用组合意义或暴力拆开都易证明）
\(\begin{aligned}f(\omega_n^k)&=\sum\limits^n_{i=0}a_i\omega_n^{\binom{i+k}{2}-\binom{i}{2}-\binom{k}{2}}\\&=\omega_n^{-\binom{k}{2}}\sum\limits^n_{i=0}a_i\omega_n^{-\binom{i}{2}}\omega_n^\binom{i+k}{2}\end{aligned}\)
考虑转为卷积的形式，不难发现\((n-i)+(i+k)=n+k\)
设\(g(x)=\sum\limits^n_{i=0}a_i\omega_n^{-\binom{i}{2}}x^{n-i}\)和\(h(x)=\sum\limits^{2n}_{i=0}\omega^{\binom{i}{2}}x^i\)
\(f(\omega_n^k)=\omega^{-\binom{k}{2}}\times([x^{n+k}]g(x)\times h(x))\)
考虑IDFT即为对所有单位根取到数后跑DFT，将上文中所有二项式系数取相反数即可。
代码较为简单，不放了
应用
一般算卷积直接拓展到\(2\)的次幂即可，需要用到的场景主要为任意长度循环卷积，即\(a_i\times b_j\rightarrow c_{(i+j)\operatorname{mod}n}\)