非常抱歉……又让您失望了呢……

2 年过去了……我还是一点进步都没有……一次大型比赛都没打好……

真的会有那样一天……像您那样强吗？……

想写的那些东西果然还是太麻烦了……根本写不动……就写一些没什么意思的东西吧……关于优化求形式幂级数的牛顿法的常数。

虽然写得很糟糕但还算是能看的，所以就发出来了。

2020年疫情期间更新了一些东西

记号约定：

$R[x]$ 表示系数属于交换环 $R$ 的关于 $x$ 的多项式环

$R[[x]]$ 表示系数属于交换环 $R$ 的关于 $x$ 的形式幂级数环

$\deg(f)=\max\{n\mid[x^n]f\neq 0\}$

$\operatorname{ord}(f)=\min\{n\mid[x^n]f\neq 0\}$

$\mathcal F_n(f)$ 为 $f \bmod (x^n - 1)$ 的长度为 $n$ 的离散 Fourier 变换

$\zeta_n$ 为 $R$ 中的 $n$ 次本原单位根

为了方便阅读，在指数部分会用 $\smallint(f)$ 表示 $\displaystyle \sum_{i=1}^\infty \frac{[x^{i-1}]f}ix^i$。

以下是废话部分，可以跳过

对于给定的精度 $n$ 和环 $R = \mathbb C$ 或 $\mathbb Z/p\mathbb Z$，$R[[x]]$ 中的形式幂级数 $f$ 被表示为一个 $R[x]$ 中的多项式 $f \bmod x^n$。

对于 $f, g \in R[x]$ ，我们可以通过 3 次 FFT 和 $n$ 次乘法用 $O(n \log n)$ 时间计算出 $fg$。对于 $f, g \in R[[x]]$ ，给定 $f \bmod x^n$ 和 $g \bmod x^n$，我们可以用和多项式乘法几乎相同的时间计算出 $fg \bmod x^n = (f \bmod x^n)(g \bmod x^n) \bmod x^n$。

Newton 法

对于形式幂级数 $f \in R[[x]], A \in R[[x]][[y]]$ ，满足 $A(f)=0$ ，令 $f_0 = f \bmod x^n$ ，那么有 $$ f \bmod x^{2n} = f_0 - \frac{A(f_0)}{A'(f_0)} \bmod x^{2n} $$

这可以通过观察 $A$ 在 $f_0$ 的 Taylor 级数得到： $$ 0 = A(f) = A(f_0) + \frac{A'(f_0)(f - f_0)^1}{1!} + \frac{A''(f_0)(f - f_0)^2}{2!} + \cdots $$

注意到 $(f - f_0)^2$ 最低非0项为 $x^{2n}$ 项，于是有 $$ \begin{align} 0 &= A(f_0) + A'(f_0)(f - f_0) \pmod{x^{2n}} \\ 0 &= \frac{A(f_0)}{A'(f_0)} + (f - f_0) \pmod{x^{2n}} \\ f &= f_0 - \frac{A(f_0)}{A'(f_0)} \pmod{x^{2n}}\tag*{$\blacksquare$} \end{align} $$

Newton 法亦可表述为，对于形式幂级数 $f \in R[[x]], A \in R[[x, y]]$ ，满足 $A(x, f)=0$ ，令 $f_0 = f \bmod x^n$ ，那么有 $$ f \bmod x^{2n} = f_0 - \frac{A(x, f_0)}{\frac{\partial A}{\partial y}(x, f_0)} \bmod x^{2n} $$

这个表述可能更容易被初学者接受。

观察式子可以发现式中 $\operatorname{ord}(A(f_0)) \geq n$，这也意味着计算中 $A'(f_0)$ 精度只需达到 $n$（当然，类似『把 $A(f_0)$ 分成 2 部分相加，分别用不同精度的 $A'(f_0)$ 计算』这样的做法是显然不可以的），后面将会看到这 2 条性质的重要性。

以下讨论每种操作的优化。对每种操作，内容分为三部分

1. 各种操作直接按照式子计算所需要的时间。我们认为长度为 $n$ 的 FFT 计算所需时间为 $\mathsf E(n)$，2 个精度为 $n$ 的形式幂级数的乘法需要 $\mathsf M(n) = (3 + o(1))\mathsf E(2n) = (6 + o(1))\mathsf E(n)$ 时间。为了方便阅读，下文操作的时间中将会省略所有 $o(1)$。
2. 用循环卷积进行优化。注意到很多情况下，我们已经得到了结果中的一部分系数，而长度为 $n$ 的 FFT 解决了循环卷积问题 $fg \bmod (x^n - 1)$，仅用于计算卷积会非常浪费。所以可以考虑先计算循环卷积，如果必要的话就进行一些处理，最后得到需要的系数。这里的时间以 2 个序列的循环卷积为单位计算，所以即使是平方也按照 $3\mathsf E$ 统计时间。在倒数部分，还会介绍这个技巧的一个特殊形式。
3. 减少 FFT 次数。容易发现很多情况下多次计算了相同的 DFT，或是可以用线性变换的性质合并几次 IDFT，这一部分考虑减少这些额外的开销。

如果需要用到其他操作，我们不使用更高级部分的结果。

倒数

1

对于 $f \in R[[x]]$，令 $g = 1/f$，求 $g$。

相当于 $A(g)=fg-1=0$，令 $g_0 = g \bmod x^n$ ，考虑到分母精度只需达到 $n$，那么有 $$ \begin{aligned} g \bmod x^{2n} &= g_0 - \frac{fg_0-1}{f} \bmod x^{2n} \\ &= g_0 - (fg_0-1)g_0 \bmod x^{2n} \\ &= 2g_0 - fg_0^2 \bmod x^{2n} \end{aligned} $$

（好像能直接得到这个式子……）

从 $g \bmod x^n$ 计算 $g \bmod x^{2n}$ 需要 1 次长度为 $2n$ 的乘法、1 次长度为 $4n$ 的乘法，用时 $18\mathsf E(n)$。所以计算 $g \bmod x^n$ 所需总时间为 $18\mathsf E(n)$。

2

对于 $f \in R[[x]]$，令 $g = 1/f$，求 $g$。

考虑 $g \bmod x^{2n} = g_0 - (fg_0-1)g_0 \bmod x^{2n}$，显然 $\deg((f \bmod x^{2n})g_0 - 1) < 3n$ ，而 $\operatorname{ord}((f \bmod x^{2n})g_0 - 1)\geq n$，所以只需要计算 $(f \bmod x^{2n})g_0 \bmod (x^{2n} - 1)$ 即可。同样计算 $(fg_0-1)g_0 \bmod x^{2n}$ 也只需要长度为 $2n$ 的循环卷积。用时 $12\mathsf E(n)$。所以计算 $g \bmod x^n$ 所需总时间为 $12\mathsf E(n)$。

3

对于 $f \in R[[x]]$，令 $g = 1/f$，求 $g$。 $$ g \bmod x^{2n} = g_0 - (fg_0-1)g_0 \bmod x^{2n} $$

迭代中有两次和 $g_0$ 相关的长度为 $2n$ 的循环卷积，可以记录下 $\mathcal F_{2n}(g_0)$ 而不是重新计算一遍。总时间为 $10\mathsf E(n) = 1\frac23 \mathsf M(n)$。

如果允许长度为 $3n$ 的 FFT，考虑 $g \bmod x^{2n} = g_0 - (fg_0^2-g_0) \bmod x^{2n}$，用长度为 $3n$ 的循环卷积计算 $fg_0^2$ 即可做到总时间 $9\mathsf E(n) = 1\frac12 \mathsf M(n)$。这个方法并没有使用特别的优化方法，但第 2 部分的模型并不支持快速计算 $fg_0^2$，所以放在第 3 部分。

但我们仍然需要一个改进的做法，因为并不一定支持长度为 $3n$ 的 FFT。另一方面需要注意的是，很多其他操作中包含倒数的迭代，每次迭代中都有其他地方（可能是下一次迭代中）需要使用 $\mathcal F_{2n}(f \bmod x^{2n})$ 或 $\mathcal F_{2n}(g_0)$，这时这个方法不比前一个做法更快。但是，只需稍加改进，这个做法即可在几乎所有情况下优于前一个做法。

我们使用长度为 $3n$ 的 FFT 是为了计算长度为 $3n$ 的循环卷积，而实际上并不是必须用循环卷积才可以解决问题。对 $a\in R,a^{2n}\neq 1$，考虑在 $R[x]/(x^{2n}-1)(x^n- a^n)$ 中计算卷积，即在 $1, \zeta_{2n}, \zeta_{2n}^2, \dots, \zeta_{2n}^{2n-1}, a, a\zeta_n, a\zeta_n^2, \dots, a\zeta_n^{n-1}$ 上多点求值和插值。对 $f \in R[x]/(x^{2n}-1)(x^n- a^n)$ 进行多点求值只需用 FFT 计算 $\mathcal F_{2n}(f)$ 和 $\mathcal F_n(f(ax))$，而插值只需分别还原并 CRT 合并。

容易发现，如果在 $R[x]/(x^{2n}-1)(x^n- a^n)$ 中进行卷积，仍然可以处理超出长度部分的影响。而这个做法不需要长度为 $3n$ 的 FFT，同时也计算了 $\mathcal F_{2n}(f \bmod x^{2n})$ 或 $\mathcal F_{2n}(g_0)$，所需时间仍是改进前的 $9\mathsf E(n) = 1\frac12 \mathsf M(n)$，所以这个做法可以几乎完全代替前一种做法。

我们可以把 $\mathcal F_{2n}(f), \mathcal F_n(f(ax))$ 记为 $\mathcal F_{2n, n}(f)$。有些时候取 $a = \zeta_{4n}$ 会比较方便，因为如果还需要计算长为 $4n$ 的循环卷积，可以直接和 $\mathcal F_n(f(\zeta_{4n}^3x))$ 合并为 $\mathcal F_{4n}(f)$，这将使实现变得简单一些。此时还可以直接计算 $\mathcal F_{4n}(f)$ 进一步简化实现。

简单描述一下思路：为了算出所需结果 $f$，先算出 $f \bmod (x^{2n}-1)(x^n- a^n)$，考虑超出部分对前n项（本应全是 $0$）的贡献，利用这些信息还原出这一部分，然后即可把这一部分对所需部分的影响消除掉。

算出结果需要在 $1, \zeta_{2n}, \zeta_{2n}^2, \dots, \zeta_{2n}^{2n-1}, a, a\zeta_n, a\zeta_n^2, \dots, a\zeta_n^{n-1}$ 上多点求值和插值，多点求值即计算 $\mathcal F_{2n}(f)$ 和 $\mathcal F_n(f(ax))$，插值即分别还原并 CRT 合并。

以上是一般情况的本质原理，实际实现可以不考虑这些，最后的推荐实现也可以这样描述。考虑将所需结果 $f$ 表示为 $a x^n + b x^{2n} + c x^{3n}$，其中 $a, b, c \in R[x]$，$\deg(a), \deg(b), \deg(c) < n$，那么可以用循环卷积计算出 $f \bmod (x^{2n} - 1)$ 和 $f \bmod (x^{n} - \mathrm i) = f(\zeta_{4n}x) \bmod (x^{n} - 1)$，也就相当于算出了 $b, a+c, \mathrm i a - b - \mathrm i c$，还原出 $a$ 即可。

商数或对数

1

商数：对于 $f, h \in R[[x]]$，令 $g = 1/f, q = hg = h/f$，求 $q$。

显然先求 $g = 1/f$，再求 $q = hg$ 即可。总时间为 $24\mathsf E(n)$。

对数：对于常数项为 $1$ 的 $f \in R[[x]]$，令 $\displaystyle g = \log f = \sum_{i=1}^\infty \frac{(-1)^{i-1}(f-1)^i}{i}$，求 $g$。

这和下面的指数都要求 $R$ 是特征为 0 且非零整数可逆的环，但有限精度时应该可以降低限制？

我们有 $$ (\log x)' = \left(-\sum_{i=1}^\infty \frac{(1-x)^i}{i}\right)' = \sum_{i=0}^\infty{(1-x)^i} = \frac{(1-(1-x))\sum_{i=0}^\infty{(1-x)^i}}{1-(1-x)} = \frac1x $$

所以 $(\log f)'=f'\log'f=f'/f$，于是求商数即可。总时间为 $24\mathsf E(n)$。

2

对于 $f, h \in R[[x]]$，令 $g = 1/f, q = hg = h/f$，求 $q$。

直接求 $g$ 再求卷积所需总时间为 $18\mathsf E(n)$。

如果不需要求 $g$，注意到 $A(q)=fq-h=0$，令 $g_0 = g \bmod x^n, h_0 = h \bmod x^n, q_0 = q \bmod x^n = g_0h_0 \bmod x^n$，有 $$ \begin{aligned} q \bmod x^{2n} &= q_0 - \frac{fq_0-h}{f} \bmod x^{2n} \\ &= q_0 - (fq_0-h)g_0 \bmod x^{2n} \end{aligned} $$

• 计算 $g_0$ 需要 $12\mathsf E(n)$ 时间
• 计算 $q_0$ 需要 $6\mathsf E(n)$ 时间
• 计算 $(fq_0-h)g_0$ 需要和倒数类似的 $12\mathsf E(n)$ 时间

所以计算 $q \bmod x^{2n}$ 总时间为 $30\mathsf E(n)$，计算 $q \bmod x^n$ 总时间为 $15\mathsf E(n)$。

3

对于 $f, h \in R[[x]]$，令 $g = 1/f, q = hg = h/f$，求 $q$。

令 $g_0 = g \bmod x^n, g_1 = (g \bmod x^{2n} - g_0) / x^n, h_0 = h \bmod x^n, h_1 = (h \bmod x^{2n} - h_0) / x^n$。

如果需要求 $g$，考虑计算 $$ q \bmod x^{2n} = (g \bmod x^{2n})(h \bmod x^{2n}) \bmod x^{2n} = g_0h_0 + (g_0h_1 + g_1h_0)x^n \bmod x^{2n} $$

• 计算 $\mathcal F_{2n}(g_0)$ 和 $g_0, g_1$ 需要 $18\mathsf E(n)$
• 计算 $\mathcal F_{2n}(g_1), \mathcal F_{2n}(h_0), \mathcal F_{2n}(h_1)$ 需要 $6\mathsf E(n)$ 时间
• 计算 $g_0h_0, g_0h_1 + g_1h_0$ 需要 $4\mathsf E(n)$ 时间

所以计算 $g \bmod x^{2n}, q \bmod x^{2n}$ 总时间为 $28\mathsf E(n)$，计算 $g \bmod x^n, q \bmod x^n$ 总时间为 $14\mathsf E(n) = 2\frac13 \mathsf M(n)$。

这里用到的技巧可以这样描述：对于 $f, g \in R[[x]]$，已知 $f \bmod x^n, g \bmod x^n, \mathcal F_n(f \bmod x^{n/2})$，那么可以用 $5\mathsf E(n)$ 时间计算出 $fg \bmod x^n$。这个技巧将在下文多次出现。

如果不需要求 $g$，仍然考虑 $$ q \bmod x^{2n} = q_0 - (fq_0-h)g_0 \bmod x^{2n} $$

相比第 2 部分的算法，可以使用更快的计算倒数的方法。计算 $q_0$ 时使用的 $\mathcal F_{2n}(g_0)$ 可以保留用于计算 $(fq_0-1)g_0$。所以计算 $q \bmod x^{2n}$ 总时间为 $24\mathsf E(n)$，计算 $q \bmod x^n$ 总时间为 $12\mathsf E(n) = 2 \mathsf M(n)$。

• 计算 $g_0$ 需要 $9\mathsf E(n)$ 时间
• 计算 $\mathcal F_{2n}(g_0), q_0$ 需要 $6\mathsf E(n)$ 时间
• 计算 $fq_0$ 需要 $6\mathsf E(n)$ 时间
• 计算 $(fq_0-h)g_0$，已知 $\mathcal F_{2n}(g_0)$，需要 $4\mathsf E(n)$ 时间

所以计算 $q \bmod x^{2n}$ 总时间为 $25\mathsf E(n)$，计算 $q \bmod x^n$ 总时间为 $12.5\mathsf E(n) = 2\frac1{12} \mathsf M(n)$。

观察 $q_0 = g_0h_0 \bmod x^n, (fq_0-h)g_0$，可以发现符合上文描述的技巧的使用条件，其中 $(fq_0-h)g_0$ 可视为计算 $((fq_0-h)/x^n)g_0$，再考虑到相同的 DFT 只需计算一次，需要 $9\mathsf E(n)$ 时间计算，总时间为 $12\mathsf E(n) = 2 \mathsf M(n)$。

平方根

1

对于 $f \in R[[x]]$，令 $g = f^{1/2}, h = 1/g = f^{-1/2}$，求 $g$。

相当于 $A(g)=g^2-f=0$，令 $g_0 = g \bmod x^n, h_0 = h \bmod x^n$ ，那么有 $$ \begin{aligned} g \bmod x^{2n} &= g_0 - \frac{g_0^2-f}{2g_0} \bmod x^{2n} \\ &= g_0 - \frac{(g_0^2-f)h_0}{2} \bmod x^{2n} \end{aligned} $$

从 $g \bmod x^n, h \bmod x^n$ 计算 $g \bmod x^{2n}$ 需要 1 次长度为 $2n$ 的乘法、1 次长度为 $4n$ 的乘法，计算 $h \bmod x^{2n}$ 需要 1 次计算倒数的迭代，用时 $36\mathsf E(n)$。所以计算 $g \bmod x^n, h \bmod x^n$ 所需总时间为 $36\mathsf E(n)$ ，如果不需要计算 $h$，可以省略最后一次迭代中的相关计算，总时间为 $27\mathsf E(n)$。

2

对于 $f \in R[[x]]$，令 $g = f^{1/2}, h = 1/g = f^{-1/2}$，求 $g$。

$$ g \bmod x^{2n} = g_0 - (g_0^2-f)h_0/2 \bmod x^{2n} $$ 计算 $g_0^2$ 需要 1 次长度为 $n$ 的循环卷积，计算 $(g_0^2-f)h_0$ 需要 1 次长度为 $2n$ 的循环卷积，计算 $h \bmod x^{2n}$ 需要 1 次计算倒数的迭代，用时 $21\mathsf E(n)$。所以计算 $g \bmod x^n, h \bmod x^n$ 所需总时间为 $21\mathsf E(n)$ ，如果不需要计算 $h$，可以省略最后一次迭代中的相关计算，总时间为 $15\mathsf E(n)$。

3

对于 $f \in R[[x]]$，令 $g = f^{1/2}, h = 1/g = f^{-1/2}$，求 $g$。

$$ g \bmod x^{2n} = g_0 - (g_0^2-f)h_0/2 \bmod x^{2n} $$

• 保留前一轮迭代计算倒数时的 $\mathcal F_{n}(g_0)$
• 计算 $g_0^2$ 需要 $\mathsf E(n)$ 时间
• 计算 $\mathcal F_{2n}(h_0), (g_0^2-f)h_0$ 需要 $6\mathsf E(n)$ 时间
• 计算 $\mathcal F_{2n}(g \bmod x^{2n}), h \bmod x^{2n}$ 需要 1 次计算倒数的迭代，已知 $\mathcal F_{2n}(h_0)$，需要 $7\mathsf E(n)$ 时间

所以计算 $g \bmod x^n, h \bmod x^n$ 所需总时间为 $14\mathsf E(n)$，如果不需要计算 $h$，可以省略最后一次迭代中的相关计算，总时间为 $10.5\mathsf E(n) = 1\frac34 \mathsf M(n)$。

此外，最后一轮中因为不需要进行计算倒数的迭代，所以不需要计算并保留 $\mathcal F_{2n}(h_0)$，观察 $(g_0^2-f)h_0$，可以发现符合讨论商数时描述的技巧的使用条件，需要 $5\mathsf E(n)$ 计算，总时间为 $10\mathsf E(n) = 1\frac23 \mathsf M(n)$。

另一个方法 是先考虑计算 $h=1/g=f^{-1/2}$，注意到 $A(h)=fh^2-1=0$，有 $$ \begin{aligned}h \bmod x^{2n} &= h_0 - \frac{fh_0^2-1}{2fh_0} \bmod x^{2n}\\&= h_0 - \frac{fh_0^3-h_0}2 \bmod x^{2n}\end{aligned} $$ 用长度为 $4n$ 的循环卷积计算 $fh_0^3$ 需要 $12\mathsf E(n)$ 时间，所以求 $h$ 的总时间为 $12\mathsf E(n) = 2 \mathsf M(n)$。

仍然是考虑 $g \bmod x^{2n} = g_0 - (g_0^2-f)h_0/2 \bmod x^{2n}$

• 计算 $\mathcal F_{2n}(f \bmod x^n), h_0$ 需要 $12\mathsf E(n)$ 时间
• 计算 $\mathcal F_{2n}(h_0), g_0=fh_0 \bmod x^n$ 需要 $4\mathsf E(n)$ 时间
• 计算 $g_0^2$ 需要 $2\mathsf E(n)$ 时间
• 计算 $(g_0^2-f)h_0$ 需要 $4\mathsf E(n)$ 时间

所以计算 $g \bmod x^{2n}$ 总时间为 $22\mathsf E(n)$，计算 $g \bmod x^n$ 总时间为 $11\mathsf E(n) = 1\frac56 \mathsf M(n)$。

指数

1

对于常数项为 $0$ 的 $f \in R[[x]]$，令 $\displaystyle g = \exp f = \sum_{i=0}^\infty \frac{f^i}{i!}, h = 1/g = 1/\exp f$，求 $g$。

相当于 $A(g)=\log g-f=0$，令 $g_0 = g \bmod x^n$ ，那么有 $$ \begin{aligned} g \bmod x^{2n} &= g_0 - \frac{\log g_0-f}{1/g_0} \bmod x^{2n} \\ &= g_0 - (\log g_0-f)g_0 \bmod x^{2n} \\ &= g_0 - g_0(\smallint{({g_0}'/g_0)}-f) \bmod x^{2n} \end{aligned} $$

从 $g \bmod x^n, h \bmod x^n$ 计算 $g \bmod x^{2n}$ 需要 1 次计算倒数的迭代，需要 1 次长度为 $2n$ 的乘法、1 次长度为 $4n$ 的乘法，计算 $h \bmod x^{2n}$ 需要 1 次计算倒数的迭代，用时 $54\mathsf E(n)$。所以计算 $g \bmod x^n, h \bmod x^n$ 所需总时间为 $54\mathsf E(n)$ ，如果不需要计算 $h$，可以省略最后一次迭代中的相关计算，总时间为 $45\mathsf E(n)$。

2

对于常数项为 $0$ 的 $f \in R[[x]]$，令 $g = \exp f, h = 1/g = 1/\exp f$，求 $g$。

首先需要改写迭代式，令 $f_0 = f \bmod x^n$。注意到 $\operatorname{ord}((\smallint{({g_0}'/g_0)}-f)g_0) \geq n$，即 $\operatorname{ord}({g_0}'/g_0-f') \geq n-1$，那么有 $g_0h_0({g_0}'/g_0-f')={g_0}'/g_0-f' \pmod {x^{2n-1}}$ $$ \begin{aligned} g \bmod x^{2n} &= g_0 - g_0(\smallint{({g_0}'/g_0)}-f) \bmod x^{2n} \\ &= g_0 - g_0\smallint{({g_0}'/g_0-f')} \bmod x^{2n} \\ &= g_0 - g_0\smallint{(g_0h_0({g_0}'/g_0-f'))} \bmod x^{2n} \\ &= g_0 - g_0\smallint{({g_0}'h_0-f'-(g_0h_0-1){f_0}')} \bmod x^{2n} \end{aligned} $$

再注意到 $\operatorname{ord}({g_0}'h_0-f'-(g_0h_0-1){f_0}')=\operatorname{ord}({g_0}'/g_0-f') \geq n-1$，左式中 $\operatorname{ord}(g_0h_0-1) \geq n$，所以 $\operatorname{ord}({g_0}'h_0-f') \geq n-1$。

计算 $g_0h_0$ 和 ${g_0}'h_0-f'$ 需要 2 次长度为 $n$ 的循环卷积，计算 $(g_0h_0-1){f_0}'$ 和 $g_0\smallint{({g_0}'h_0-f'-(g_0h_0-1){f_0}')}$ 需要 2 次长度为 $2n$ 的循环卷积，所以从 $g \bmod x^n, h \bmod x^n$ 计算 $g \bmod x^{2n}$ 用时 $18\mathsf E(n)$。计算 $h \bmod x^{2n}$ 需要 1 次计算倒数的迭代，所以总时间为 $30\mathsf E(n)$。如果不需要计算 $h$ ，可以省略最后一次迭代中的相关计算，总时间为 $24\mathsf E(n)$。

3

对于常数项为 $0$ 的 $f \in R[[x]]$，令 $g = \exp f, h = 1/g = 1/\exp f$，求 $g$。 $$ g \bmod x^{2n} = g_0 - g_0\smallint{({g_0}'h_0-f'-(g_0h_0-1){f_0}')} \bmod x^{2n} $$

• 保留前一轮迭代计算的 $\mathcal F_{n}(g_0)$
• 计算 $\mathcal F_{n}(h_0), \mathcal F_{2n}(h_0)$ 需要 $2\mathsf E(n)$ 时间
• 计算 $g_0h_0$ 需要 $\mathsf E(n)$ 时间
• 计算 ${g_0}’h_0 \bmod (x^n - 1)$ 需要 $2\mathsf E(n)$ 时间
• 计算 $\mathcal F_{2n}(g_0)$，已知 $\mathcal F_{n}(g_0)$，需要 $\mathsf E(n)$ 时间
• 计算 $(g_0h_0 - 1){f_0}' \bmod (x^{2n} - 1)$ 需要 $6\mathsf E(n)$ 时间
• 计算 $g_0\smallint{({g_0}'h_0-f'-(g_0h_0-1){f_0}')} \bmod (x^{2n} - 1)$ 需要 $4\mathsf E(n)$ 时间
• 计算 $\mathcal F_{2n}(g \bmod x^{2n}), h \bmod x^{2n}$ 需要 1 次计算倒数的迭代，已知 $\mathcal F_{2n}(h_0)$，需要 $8\mathsf E(n)$ 时间

所以总时间为 $24\mathsf E(n)$。如果不需要计算 $h$ ，可以省略最后一次迭代中的相关计算，总时间为 $20\mathsf E(n) = 3\frac13 \mathsf M(n)$。

因为写得比较早，所以似乎仍然可以继续进行不少优化……但就这样吧，因为还有更好的做法。

另一个方法 类似上面的改写，有 $$ \begin{aligned} g \bmod x^{2n} &= g_0 - g_0(\smallint{({g_0}'/g_0)}-f) \bmod x^{2n} \\ &= g_0 - g_0(\smallint{({g_0}'/g_0-f_0'+f_0')}-f) \bmod x^{2n} \\ &= g_0 - g_0(\smallint{(g_0h_0({g_0}'/g_0-f_0')+f_0')}-f) \bmod x^{2n} \\ &= g_0 - g_0(\smallint{(h_0({g_0}'-g_0f_0')+f_0')}-f) \bmod x^{2n} \end{aligned} $$ 其中 $\operatorname{ord}(g_0'-g_0f_0') \geq n$，因为 $(\exp(f))'=\exp(f)f'$，那么有

• 保留前一轮迭代计算的 $\mathcal F_{n, n/2}(g_0)$
• 计算 $g_0f_0'$ 需要 $2\mathsf E(n)$ 时间
• 计算 $\mathcal F_{2n}(h_0), h_0({g_0}'-g_0f_0')$ 需要 $6\mathsf E(n)$ 时间
• 计算 $\mathcal F_{2n}(g_0)$，已知 $\mathcal F_{n, n/2}(g_0)$，需要 $0.5\mathsf E(n)$ 时间
• 计算 $g_0(\smallint{(h_0({g_0}'-g_0f_0')+f_0')}-f)$ 需要 $4\mathsf E(n)$ 时间
• 计算 $\mathcal F_{2n,n}(g_0 \bmod x^{2n}), h \bmod x^{2n}$ 需要 1 次计算倒数的迭代，已知 $\mathcal F_{2n}(h_0)$，需要 $7\mathsf E(n)$ 时间

所以总时间为 $19.5\mathsf E(n)$。如果不需要计算 $h$ ，可以省略最后一次迭代中的相关计算，总时间为 $16\mathsf E(n) = 2\frac23 \mathsf M(n)$。

此外，最后一轮中因为不需要进行计算倒数的迭代，所以不需要计算并保留 $\mathcal F_{2n}(h_0)$，观察 $h_0({g_0}'-g_0f_0')$，可以发现符合讨论商数时描述的技巧的使用条件，所以可以用 $5\mathsf E(n)$ 时间计算，这样总时间为 $15.5\mathsf E(n) = 2\frac7{12} \mathsf M(n)$。

下面是发现循环卷积优化后的较重要的文章。除了以上内容以外，还有一类基于分块的优化，可以得到一些更好的结果。如果有兴趣的话，似乎可以在这些地方找到进一步优化的方法？

Removing redundancy in high-precision Newton iteration

Newton iteration revisited

Newton's method and FFT trading

Faster algorithms for the square root and reciprocal of power series

Faster exponentials of power series

A simple and fast algorithm for computing exponentials of power series

Fast algorithms for elementary operations on complex power series

A note on the fast power series' exponential