题解 P5432/基于科学计数法的 FFT 优化高精
warzone
·
·
题解
可能更好的阅读体验
本文将介绍基于科学计数法的方法，使用 FFT 优化高精度除法、开根、指数、对数等。
对于多项式
f(x)=f_0+f_1x+f_2x^2+f_3x^3+\cdots
对于高精度整数，通常是将其表示为 f(10) 的形式，如
3579=9+7\times 10+5\times 10^2+3\times 10^3
但这一方法不能较好地表示小数。
考虑科学计数法，将每个数表示为 f(10^{-1})\times10^n 的形式，如
158.97=1.5897\times 10^2
=(1+5\times 10^{-1}+8\times 10^{-2}+9\times 10^{-3}+7\times 10^{-4})\times 10^2
由此我们得到了高精度小数的表示方法。
高精度小数的乘法
(f(10^{-1})\times 10^n)\times(g(10^{-1})\times 10^m)=(f\times g)(10^{-1})\times 10^{n+m}
FFT 优化即可，注意进位跟整数是反过来的。
高精度小数的倒数
对于高精度整数，求倒数显然是不可能的。
但高精度小数可以，根据多项式求逆：
a(x)f(x)\equiv 1\pmod{x^n}
a(x)\equiv 1\pmod{x^{\frac{n}{2}}}
f(x)\equiv g(x)(2-a(x)g(x))\pmod{x^n}
但我们无法使用多项式求逆的终止条件 (a_0f_0=1)，
考虑将同余式展开并代入
A=a(10^{-1}),F=f(10^{-1}),G=g(10^{-1})
AF=1-10^{-n}C_0,C_0\in[0,1)
AG=1-10^{-\frac{n}{2}}C,C\in[0,1)
1-2AG+A^2G^2=10^{-n}C^2,C^2\in[0,1)
F^2-2FG+G^2=(1-10^{-n}C_0)10^{-n}C,C\in[0,1)
F=G(2-AG)-10^{-n}C,C\in[0,1)
选择 [0,1) 而非 [0,10) 是为了避免进位的情况。
终止条件是 n=2，此时 F=10^{-1}{\left\lfloor\dfrac{100}{10a_0+a_1}\right\rfloor}。
高精度小数的除法
\dfrac{f(10^{-1})\times 10^n}{g(10^{-1})\times 10^m}=f(10^{-1})g^{-1}(10^{-1})\times 10^{n-m}
计算出 f(10^{-1})g^{-1}(10^{-1}) 即可。
整除保留整数即可，可能有 1 的误差，需要作出调整。
可以发现，这一做法跟多项式除法“先翻转再求逆”的方法是一致的，
实际上体现了多项式除法的直观意义。
高精度开根
开根可以使用牛顿迭代法计算
x^2-a=0
x=\dfrac{x_0}{2}+\dfrac{a}{2x_0}
每迭代一次精度翻倍，结合倍增可以 \Theta(n\log n) 求出。
高精度 ln 和 exp
与多项式 ln 和 exp 不同的是，\ln f(x)=\displaystyle\int^x\dfrac{f'(t)}{f(t)}\mathrm{d}t 没法用了。
这里搬一下 WC2012《理性愉悦: 高精度数值计算》中的原内容，对于数列
a_0=a,b_0=b,a_{n+1}=\dfrac{a_n+b_n}{2},b_{n+1}=\sqrt{a_nb_n}\quad(n\in \mathbf{N})
则 \displaystyle \lim_{n\rightarrow\infty}a_n=\lim_{n\rightarrow\infty}b_n=\dfrac{\pi}{2}{\left(\int_0^{\frac{\pi}{2}}\dfrac{\mathrm{d}x}{\sqrt{a^2\cos^2x+b^2\sin^2x}}\right)}^{-1}，
且跟牛顿迭代一样误差是平方级别的缩小。
称这一极限为 a,b 的算术几何平均数，记为\operatorname{AG}(a,b) 。它有如下性质：
\forall x\ge 4,{\left|\dfrac{\pi}{2\operatorname{AG}{\left(1,\dfrac{4}{x}\right)}}-\ln x\right|}\le\dfrac{64}{x^2}{\left(8+\ln\dfrac{x}{4}\right)}
$$\lim_{n\rightarrow\infty} \dfrac{4a_n^2}{1-\displaystyle\sum_{k=0}^n2^k(a_k-b_k)^2}=\pi$$
同样误差是平方级别的缩小。
对于较大的 $x$，可以通过计算 $\dfrac{\pi}{2\operatorname{AG}{\left(1,\dfrac{4}{x}\right)}}$ 达到 $\lfloor\log_{10}x\rfloor$ 的精度。
对于较小的 $x$，
- 若 $x>1$，可以通过 $\ln x=\dfrac{1}{2}\ln x^2$ 放大 $x$ 来提高精度。
- 否则，计算出 $\ln 10$ 后，通过 $\ln x=\ln (10^mx)-m\ln 10$ 提高精度。
时间复杂度 $\Theta(n\log^2 n)$。
有了 ln 后，exp 也就可用牛顿迭代求得。
## 总结
相比于仅仅是将整数换为小数，就能更有效地解决乘除、开根一类的问题。
由此可见，看待问题的角度，有时比解决问题的方法更为重要。