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

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

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

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

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

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

记号约定：

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

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

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

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

${\mathcal{F}}_n(f)$ 为 $fmod(x^n-1)$ 的长度为 $n$ 的离散 Fourier 变换

${\zeta }_n$ 为 $R$ 中的 $n$ 次本原单位根

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

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

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

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

Newton 法

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

这可以通过观察 $A$ 在 $f_0$ 的 Taylor 级数得到： $$0=A(f)=A(f_0)+\frac{A^{\prime }(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{array}{rl}0& =A(f_0)+A^{\prime }(f_0)(f-f_0)(\mathrm{mod}{x}^{2n})\\ 0& =\frac{A(f_0)}{A^{\prime }(f_0)}+(f-f_0)(\mathrm{mod}{x}^{2n})\\ ◼& f& =f_0-\frac{A(f_0)}{A^{\prime }(f_0)}(\mathrm{mod}{x}^{2n})\end{array}$$

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

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

观察式子可以发现式中 $\mathrm{ord}(A(f_0))\ge n$，这也意味着计算中 $A^{\prime }(f_0)$ 精度只需达到 $n$（当然，类似『把 $A(f_0)$ 分成 2 部分相加，分别用不同精度的 $A^{\prime }(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 解决了循环卷积问题 $fgmod(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=gmod{x}^n$ ，考虑到分母精度只需达到 $n$，那么有 $$\begin{array}{rl}gmod{x}^{2n}& =g_0-\frac{f{g}_0-1}{f}mod{x}^{2n}\\ & =g_0-(f{g}_0-1)g_{0}mod{x}^{2n}\\ & =2g_0-f{g}_0^{2}mod{x}^{2n}\end{array}$$

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

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

2

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

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

3

对于 $f\in R[[x]]$，令 $g=1/f$，求 $g$。 $$gmod{x}^{2n}=g_0-(f{g}_0-1)g_{0}mod{x}^{2n}$$

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

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

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

我们使用长度为 $3n$ 的 FFT 是为了计算长度为 $3n$ 的循环卷积，而实际上并不是必须用循环卷积才可以解决问题。对 $a\in R,a^{2n}\ne 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}(fmod{x}^{2n})$ 或 ${\mathcal{F}}_{2n}(g_0)$，所需时间仍是改进前的 $9\mathsf{E}(n)=1\frac{1}{2}\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}^{3}x))$ 合并为 ${\mathcal{F}}_{4n}(f)$，这将使实现变得简单一些。此时还可以直接计算 ${\mathcal{F}}_{4n}(f)$ 进一步简化实现。

简单描述一下思路：为了算出所需结果 $f$，先算出 $fmod(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]$，$\mathrm{deg}(a),\mathrm{deg}(b),\mathrm{deg}(c)<n$，那么可以用循环卷积计算出 $fmod(x^{2n}-1)$ 和 $fmod(x^n-\mathrm{i})=f({\zeta }_{4n}x)mod(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}^{\mathrm{\infty }}\frac{(-1{)}^{i-1}(f-1{)}^i}{i}}$，求 $g$。

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

我们有 $$(\log x{)}^{\prime }={(-\sum _{i=1}^{\mathrm{\infty }}\frac{(1-x{)}^i}{i})}^{\prime }=\sum _{i=0}^{\mathrm{\infty }}(1-x{)}^i=\frac{(1-(1-x))\sum _{i=0}^{\mathrm{\infty }}(1-x{)}^i}{1-(1-x)}=\frac{1}{x}$$

所以 $(\log f{)}^{\prime }=f^{\prime }{\log }^{\prime }f=f^{\prime }/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=gmod{x}^n,h_0=hmod{x}^n,q_0=qmod{x}^n=g_0{h}_{0}mod{x}^n$，有 $$\begin{array}{rl}qmod{x}^{2n}& =q_0-\frac{f{q}_0-h}{f}mod{x}^{2n}\\ & =q_0-(f{q}_0-h)g_{0}mod{x}^{2n}\end{array}$$

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

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

3

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

令 $g_0=gmod{x}^n,g_1=(gmod{x}^{2n}-g_0)/x^n,h_0=hmod{x}^n,h_1=(hmod{x}^{2n}-h_0)/x^n$。

如果需要求 $g$，考虑计算 $$qmod{x}^{2n}=(gmod{x}^{2n})(hmod{x}^{2n})mod{x}^{2n}=g_0{h}_0+(g_0{h}_1+g_1{h}_0)x^{n}mod{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_0{h}_0,g_0{h}_1+g_1{h}_0$ 需要 $4\mathsf{E}(n)$ 时间

所以计算 $gmod{x}^{2n},qmod{x}^{2n}$ 总时间为 $28\mathsf{E}(n)$，计算 $gmod{x}^n,qmod{x}^n$ 总时间为 $14\mathsf{E}(n)=2\frac{1}{3}\mathsf{M}(n)$。

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

如果不需要求 $g$，仍然考虑 $$qmod{x}^{2n}=q_0-(f{q}_0-h)g_{0}mod{x}^{2n}$$

相比第 2 部分的算法，可以使用更快的计算倒数的方法。计算 $q_0$ 时使用的 ${\mathcal{F}}_{2n}(g_0)$ 可以保留用于计算 $(f{q}_0-1)g_0$。所以计算 $qmod{x}^{2n}$ 总时间为 $24\mathsf{E}(n)$，计算 $qmod{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)$ 时间
• 计算 $f{q}_0$ 需要 $6\mathsf{E}(n)$ 时间
• 计算 $(f{q}_0-h)g_0$，已知 ${\mathcal{F}}_{2n}(g_0)$，需要 $4\mathsf{E}(n)$ 时间

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

观察 $q_0=g_0{h}_{0}mod{x}^n,(f{q}_0-h)g_0$，可以发现符合上文描述的技巧的使用条件，其中 $(f{q}_0-h)g_0$ 可视为计算 $((f{q}_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=gmod{x}^n,h_0=hmod{x}^n$ ，那么有 $$\begin{array}{rl}gmod{x}^{2n}& =g_0-\frac{g_0^2-f}{2g_0}mod{x}^{2n}\\ & =g_0-\frac{(g_0^2-f)h_0}{2}mod{x}^{2n}\end{array}$$

从 $gmod{x}^n,hmod{x}^n$ 计算 $gmod{x}^{2n}$ 需要 1 次长度为 $2n$ 的乘法、1 次长度为 $4n$ 的乘法，计算 $hmod{x}^{2n}$ 需要 1 次计算倒数的迭代，用时 $36\mathsf{E}(n)$。所以计算 $gmod{x}^n,hmod{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$。

$$gmod{x}^{2n}=g_0-(g_0^2-f)h_0/2mod{x}^{2n}$$ 计算 $g_0^2$ 需要 1 次长度为 $n$ 的循环卷积，计算 $(g_0^2-f)h_0$ 需要 1 次长度为 $2n$ 的循环卷积，计算 $hmod{x}^{2n}$ 需要 1 次计算倒数的迭代，用时 $21\mathsf{E}(n)$。所以计算 $gmod{x}^n,hmod{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$。

$$gmod{x}^{2n}=g_0-(g_0^2-f)h_0/2mod{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}(gmod{x}^{2n}),hmod{x}^{2n}$ 需要 1 次计算倒数的迭代，已知 ${\mathcal{F}}_{2n}(h_0)$，需要 $7\mathsf{E}(n)$ 时间

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

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

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

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

• 计算 ${\mathcal{F}}_{2n}(fmod{x}^n),h_0$ 需要 $12\mathsf{E}(n)$ 时间
• 计算 ${\mathcal{F}}_{2n}(h_0),g_0=f{h}_{0}mod{x}^n$ 需要 $4\mathsf{E}(n)$ 时间
• 计算 $g_0^2$ 需要 $2\mathsf{E}(n)$ 时间
• 计算 $(g_0^2-f)h_0$ 需要 $4\mathsf{E}(n)$ 时间

所以计算 $gmod{x}^{2n}$ 总时间为 $22\mathsf{E}(n)$，计算 $gmod{x}^n$ 总时间为 $11\mathsf{E}(n)=1\frac{5}{6}\mathsf{M}(n)$。

指数

1

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

相当于 $A(g)=\log g-f=0$，令 $g_0=gmod{x}^n$ ，那么有 $$\begin{array}{rl}gmod{x}^{2n}& =g_0-\frac{\log g_0-f}{1/g_0}mod{x}^{2n}\\ & =g_0-(\log g_0-f)g_{0}mod{x}^{2n}\\ & =g_0-g_0(\int ({g_0}^{\prime }/g_0)-f)mod{x}^{2n}\end{array}$$

从 $gmod{x}^n,hmod{x}^n$ 计算 $gmod{x}^{2n}$ 需要 1 次计算倒数的迭代，需要 1 次长度为 $2n$ 的乘法、1 次长度为 $4n$ 的乘法，计算 $hmod{x}^{2n}$ 需要 1 次计算倒数的迭代，用时 $54\mathsf{E}(n)$。所以计算 $gmod{x}^n,hmod{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=fmod{x}^n$。注意到 $\mathrm{ord}((\int ({g_0}^{\prime }/g_0)-f)g_0)\ge n$，即 $\mathrm{ord}({g_0}^{\prime }/g_0-f^{\prime })\ge n-1$，那么有 $g_0{h}_0({g_0}^{\prime }/g_0-f^{\prime })={g_0}^{\prime }/g_0-f^{\prime }(\mathrm{mod}{x}^{2n-1})$ $$\begin{array}{rl}gmod{x}^{2n}& =g_0-g_0(\int ({g_0}^{\prime }/g_0)-f)mod{x}^{2n}\\ & =g_0-g_0\int ({g_0}^{\prime }/g_0-f^{\prime })mod{x}^{2n}\\ & =g_0-g_0\int (g_0{h}_0({g_0}^{\prime }/g_0-f^{\prime }))mod{x}^{2n}\\ & =g_0-g_0\int ({g_0}^{\prime }{h}_0-f^{\prime }-(g_0{h}_0-1){f_0}^{\prime })mod{x}^{2n}\end{array}$$

再注意到 $\mathrm{ord}({g_0}^{\prime }{h}_0-f^{\prime }-(g_0{h}_0-1){f_0}^{\prime })=\mathrm{ord}({g_0}^{\prime }/g_0-f^{\prime })\ge n-1$，左式中 $\mathrm{ord}(g_0{h}_0-1)\ge n$，所以 $\mathrm{ord}({g_0}^{\prime }{h}_0-f^{\prime })\ge n-1$。

计算 $g_0{h}_0$ 和 ${g_0}^{\prime }{h}_0-f^{\prime }$ 需要 2 次长度为 $n$ 的循环卷积，计算 $(g_0{h}_0-1){f_0}^{\prime }$ 和 $g_0\int ({g_0}^{\prime }{h}_0-f^{\prime }-(g_0{h}_0-1){f_0}^{\prime })$ 需要 2 次长度为 $2n$ 的循环卷积，所以从 $gmod{x}^n,hmod{x}^n$ 计算 $gmod{x}^{2n}$ 用时 $18\mathsf{E}(n)$。计算 $hmod{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$。 $$gmod{x}^{2n}=g_0-g_0\int ({g_0}^{\prime }{h}_0-f^{\prime }-(g_0{h}_0-1){f_0}^{\prime })mod{x}^{2n}$$

• 保留前一轮迭代计算的 ${\mathcal{F}}_n(g_0)$
• 计算 ${\mathcal{F}}_n(h_0),{\mathcal{F}}_{2n}(h_0)$ 需要 $2\mathsf{E}(n)$ 时间
• 计算 $g_0{h}_0$ 需要 $\mathsf{E}(n)$ 时间
• 计算 ${g_0}^{\prime }{h}_{0}mod(x^n-1)$ 需要 $2\mathsf{E}(n)$ 时间
• 计算 ${\mathcal{F}}_{2n}(g_0)$，已知 ${\mathcal{F}}_n(g_0)$，需要 $\mathsf{E}(n)$ 时间
• 计算 $(g_0{h}_0-1){f_0}^{\prime }mod(x^{2n}-1)$ 需要 $6\mathsf{E}(n)$ 时间
• 计算 $g_0\int ({g_0}^{\prime }{h}_0-f^{\prime }-(g_0{h}_0-1){f_0}^{\prime })mod(x^{2n}-1)$ 需要 $4\mathsf{E}(n)$ 时间
• 计算 ${\mathcal{F}}_{2n}(gmod{x}^{2n}),hmod{x}^{2n}$ 需要 1 次计算倒数的迭代，已知 ${\mathcal{F}}_{2n}(h_0)$，需要 $8\mathsf{E}(n)$ 时间

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

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

另一个方法 类似上面的改写，有 $$\begin{array}{rl}gmod{x}^{2n}& =g_0-g_0(\int ({g_0}^{\prime }/g_0)-f)mod{x}^{2n}\\ & =g_0-g_0(\int ({g_0}^{\prime }/g_0-f_0^{\prime }+f_0^{\prime })-f)mod{x}^{2n}\\ & =g_0-g_0(\int (g_0{h}_0({g_0}^{\prime }/g_0-f_0^{\prime })+f_0^{\prime })-f)mod{x}^{2n}\\ & =g_0-g_0(\int (h_0({g_0}^{\prime }-g_0{f}_0^{\prime })+f_0^{\prime })-f)mod{x}^{2n}\end{array}$$ 其中 $\mathrm{ord}(g_0^{\prime }-g_0{f}_0^{\prime })\ge n$，因为 $(\exp (f){)}^{\prime }=\exp (f)f^{\prime }$，那么有

• 保留前一轮迭代计算的 ${\mathcal{F}}_{n,n/2}(g_0)$
• 计算 $g_0{f}_0^{\prime }$ 需要 $2\mathsf{E}(n)$ 时间
• 计算 ${\mathcal{F}}_{2n}(h_0),h_0({g_0}^{\prime }-g_0{f}_0^{\prime })$ 需要 $6\mathsf{E}(n)$ 时间
• 计算 ${\mathcal{F}}_{2n}(g_0)$，已知 ${\mathcal{F}}_{n,n/2}(g_0)$，需要 $0.5\mathsf{E}(n)$ 时间
• 计算 $g_0(\int (h_0({g_0}^{\prime }-g_0{f}_0^{\prime })+f_0^{\prime })-f)$ 需要 $4\mathsf{E}(n)$ 时间
• 计算 ${\mathcal{F}}_{2n,n}(g_{0}mod{x}^{2n}),hmod{x}^{2n}$ 需要 1 次计算倒数的迭代，已知 ${\mathcal{F}}_{2n}(h_0)$，需要 $7\mathsf{E}(n)$ 时间

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

此外，最后一轮中因为不需要进行计算倒数的迭代，所以不需要计算并保留 ${\mathcal{F}}_{2n}(h_0)$，观察 $h_0({g_0}^{\prime }-g_0{f}_0^{\prime })$，可以发现符合讨论商数时描述的技巧的使用条件，所以可以用 $5\mathsf{E}(n)$ 时间计算，这样总时间为 $15.5\mathsf{E}(n)=2\frac{7}{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