视角的变化：重新理解 FFT

最近重新理解了一下 FFT，想写一点不容易解释清楚的东西。

首先，与传统的求点值不同的是，我将 \(\operatorname{DFT}\) 理解为另一种等价的形式：\(\sum\frac{f_i}{1-\omega_n^ix}\)。

这是一个分治 FFT 的形式，下面我将分别提出两种求这个和的方式，分别对应了 DIT 和 DIF 两种算法。

DIT

我们观察到一个事实，\(\prod\limits_{i=0}^{n - 1}(1 - \omega_n^i x)=1 - x^n\)。

我们试图分治，于是考虑按照 \(i\) 的奇偶分成两半，先对两部分运行该算法于是能得到 \(\frac{F(x)}{1-x^{n/2}}\) 以及 \(\frac{G(x)}{1-x^{n/2}}\)。

由于右半边应当是奇数但我们当作偶数做了，所以应当把 \(x\) 还原成 \(\omega_nx\)，于是就是 \(\frac{G(\omega_nx)}{1-\omega_n^{n/2}x^{n/2}}=\frac{G(\omega_nx)}{1+x^{n/2}}\)。于是 \(F(x)\) 和 \(G(\omega_nx)\) 就可以通分合并成当前的答案。

这样的分治结构的底层就是蝴蝶变换的顺序，如果每个分治节点都存储一个多项式，自下而上观察整个过程，每次乘单位根对应换元，加减法就是通分求和的过程。

DIF

让我们换个视角，我们考虑自上而下做维护每一处的贡献。

考虑把这些数按照大小分成两部分，对于大的一部分，把它们写成 \(n / 2 + i\) 的形式。考虑到 \(\omega_n^{n/2} = -1, (\omega_n^{n/2})^2 = 1\) 那么大的一部分在所有的奇数次项会全部有 \(-1\) 的系数，对于偶数位置和小的部分系数一致。所以考虑把两部分相加得到的数组分治下去，就能获得偶数次项的系数。用小的部分剪去大的部分后乘上 \(x\) 次幂带来的系数（就是 \(\frac{1}{1-\omega_n^ix}\) 里的 \(\omega_n^i\)），分治下去就能获得奇数次项的系数。

关于 yhx-12243 的写法

其实我上一篇博客只讨论了这一部分，我这里来重复一遍之前的结论，那种写法是将 DIT 和 DIF 再额外蝴蝶变换一次来减少指针移动的次数，是一种常数优化。