从论文哥的博客学习了牛顿法的优化。

假设在 $\mathbb{F}_{p}$ 中运算，其中 $p$ 为素数。

令 $\mathcal{F}_{n}(f)$ 表示 $f$ 的 $n$ 长 DFT， $\deg f$ 为 $f$ 的最高次数。

回顾 FFT 的过程，设 $f\bmod x^8-1=f_0+f_1x+f_2x^2+f_3x^3+f_4x^4+f_5x^5+f_6x^6+f_7x^7$ ，那么 $f\bmod x^4-1=(f_0+f_4)+(f_1+f_5)x+(f_2+f_6)x^2+(f_3+f_7)x^3$ ， $f\bmod x^4+1=(f_0-f_4)+(f_1-f_5)x+(f_2-f_6)x^2+(f_3-f_7)x^3$ ，更一般的可以写为 $f\bmod x^{2n}-r^2$ 可以分解为 $f\bmod x^n-r$ 与 $f\bmod x^n+r$ ，而 $r$ 如果取到单位根，发现这就是 radix-2 FFT ！显然可以发现如果 $\deg f=n-1$ 和 $\deg g=2n-1$ 的 $fg \bmod x^{2n}-1$ 的前几项会产生“混叠”，但是牛顿法中恰恰前几项是提前知道的，不需要计算，而且可以还原出正确的 $fg$ （这里也有 $\bmod x^{?}-1$ 但是因为一个周期内和非周期是一样的就无视吧）。

倒数

$g=1/f$ 且 $[x^0]f$ 可逆，求 $g \bmod{x^k}$ （前 $k$ 项），设 $g_0=g\bmod{x^n}$ 。

有 $g\equiv g_0-(fg_0-1)g_0\pmod{x^{2n}}$ ，求出 $\mathcal{F}_{2n}(g_0),\mathcal{F}_{2n}(f\bmod{x^{2n}})$ ，然后求出 $fg_0\bmod{x^{2n}-1}$ 发现 $fg_0-1\equiv 0\pmod{x^n}$ 而混叠项只会在前 $n-1$ 项中，都设为 $0$ 即求得 $(fg_0-1) \bmod{x^{2n}}$ ，求 $\mathcal{F}_{2n}((fg_0-1) \bmod{x^{2n}}),\mathcal{F}_{2n}(g_0)$ ，发现 $\mathcal{F}_{2n}(g_0)$ 之前求过了，可以复用，再次相乘， IDFT 并消除影响（一般是减去混叠的值）即求得 $(fg_0-1)g_0\bmod{x^{2n}}$ 显然前半部分为 $0$ 其实不需要，对后半部分取负数复制到原先 $g_0$ 后面就得到了 $g\bmod{x^{2n}}$ 。

更难的那个插值没看懂就不会。。

商数/对数

对数： $g=\ln f$ 且 $[x^0]f=1$ ，求 $g \bmod{x^k}$ ，等价于求 $\int(f'/f)$ 还是求商的问题，直接乘以 $1/f$ 即可，但是可能比较慢。

商数（不带余除法）： $q=h/f$ ，且 $[x^0]f$ 可逆，求 $q \bmod{x^k}$ ，设 $g=1/f,g_0=g\bmod{x^n},q_0=q\bmod{x^n}$ 。

有 $q\equiv q_0-(fq_0-h)g_0\pmod{x^{2n}}$ ，考虑求出 $q_0$ 需要求出 $g_0,\mathcal{F}_{2n}(g_0),\mathcal{F}_{2n}(h\bmod{x^n})$ ，求出 $q_0$ 后，发现 $fq_0-h\equiv 0\pmod{x^n}$ ，于是求 $\mathcal{F}_{2n}(q_0),\mathcal{F}_{2n}(f\bmod{x^{2n}}),fq_0$ ，将 $fq_0$ 的前 $n$ 项直接设为 $0$ ，后 $n$ 项对应减去 $h$ 的对应项即 $fq_0-h\bmod{x^{2n}}$ ， $\mathcal{F}_{2n}(g_0)$ 之前求过可复用，与倒数最后用相同方法即可，这样对数也可以用这个算法啦。

指数

$g=\exp f$ 且 $[x^0]f=0$ ，求 $g \bmod{x^k}$ ，设 $h=1/g=1/{\exp f}$ ，设 $h_0=h\bmod{x^n},g_0=g\bmod{x^n},f_0=f\bmod{x^n}$ 。

可知 $[x^0]g=1,[x^1]g=[x^1]f$ ，有 $g\equiv g_0-g_0(\int(h_0(g_0'-g_0f_0')+f_0')-f)\pmod{x^{2n}}$ ，显然 $\exp'f=f'\exp f$ ，最内层括号中有 $g_0f_0'$ ，发现 $g_0f_0'\equiv g_0'\pmod{x^{n-1}}$ ，而 $\deg g_0=n-1,\deg f_0'=n-2$ ，而又知道 $g_0f_0'$ 的前 $n-1$ 项，混叠项长度是 $(n+n-1-1)-n=n-2$ ，可以消除影响，于是求 $\mathcal{F}_{n}(g_0),\mathcal{F}_{n}(f_0')$ 并消除影响即可（消除影响后还原长度），求 $\mathcal{F}_{2n}(h_0),\mathcal{F}_{2n}(g_0'-g_0f_0')$ ，继续消除影响即可，注意到后面需要加上 $f_0'$ 再积分，再减去 $f\bmod{x^{2n}}$ ，其实前半部分就还是 $0$ ，没必要对前半部分进行操作，对后半部分操作即可（注意边界即可），此时最后乘以 $g_0$ 并消除影响即可，要求 $\mathcal{F}_{2n}(g_0)$ ，已经有 $\mathcal{F}_{n}(g_0)$ ，但是这样很麻烦，于是先求出 $\mathcal{F}_{2n}(g_0)$ ，前面使用 $\mathcal{F}_{n}(g_0)$ 更方便，如果使用 dif-fft 与 dit-fft 结合，发现 $\mathcal{F}_{2n}(g_0)$ 的前 $n$ 项即为 $\mathcal{F}_{n}(g_0)$ ，后面需要一次求倒数的迭代，发现需要 $\mathcal{F}_{2n}(g)$ ，而下一次循环中需要的是 $\mathcal{F}_{4n}(g)$ ，于是在求倒数的迭代中求出 $\mathcal{F}_{4n}(g)$ 给下一次迭代使用（下一次就是 $\mathcal{F}_{2n}(g_0)$ 了），这样前面就不需要求关于 $g_0$ 的 dft 了，如果最后不需要一并求 $h$ ，可以省略最后一次迭代，如果需要求 $h$ ，最后一次求倒数的迭代也只需要 $\mathcal{F}_{2n}(g)$ 。

平方根

$g=\sqrt{f}$ 且 $[x^0]f\text{ is quadratic residue},[x^0]f\neq 0$ ，求 $g \bmod{x^k}$ ，设 $h=1/g$ ，设 $h_0=h\bmod{x^n},g_0=g\bmod{x^n}$ 。

有 $[x^0]g=\sqrt{[x^0]f}$ ，用二次剩余求出即可， $g \equiv g_0-(g_0^2-f)h_0/2\pmod{x^{2n}}$ ，发现 $g_0^2\equiv f\pmod{x^n}$ ，混叠部分长度为 $(n+n-1)-n=n-1$ ，可以消除影响（并还原长度），只需要 $\mathcal{F}_{n}(g_0)$ ，然后需要 $\mathcal{F}_{2n}(h_0),\mathcal{F}_{2n}(g_0^2-f)$ ，与求倒数时的操作相同，最后需要一次求倒数的迭代，发现需要 $\mathcal{F}_{2n}(g\bmod{x^{2n}})$ ，可以保留到下一次迭代中使用，上面就不需要求 $\mathcal{F}_{n}(g_0)$ 了，如果最后不需要求 $h$ ，可省略最后一次迭代。