牛顿迭代法求高精度除法

· · 题解

前置知识：高精度乘法（FFT/NTT），导数。

推销我的高精度四则运算：从入门到入土。

牛顿迭代法

牛顿迭代法可以用于求取函数零点。具体的，我们以 f(x)=2x^2-1 详细说明：

  1. 随便选取一个 x_0 作为起始值（我选 x_0 = 1），得到 A(x_0,f(x_0))。

  1. 作 A 点的切线交 x 轴于 B。

  1. 把 x_B 当作 1 中的 x_0，继续迭代。

这里我们迭代了 3 次得到了 F 点，而计算器给的值是 0.7071067811865475，可以看到精度已经来到了 10^{-5}，精度提升得非常快。

牛顿迭代法求 A/B

假设要求 \left\lfloor \frac a b \right\rfloor，那么我们要考虑求出 \frac 1b。

显然这个 \frac 1 b 是一个小数，而由于我们只需要取整数，所以我们只需要计算出 \frac 1 b 的 O(\text{len}_a) 位。

如何计算？我们考虑牛顿迭代，设 x 为要求的数：

x &= \frac 1 b \end{align*}

也就是 f(x)=x-\frac1b 的零点。

但是这个东西是一次的，做了切线还是自己。于是我们考虑倒反天罡，求 g(x) = b - \frac1 x 的零点。

作切线显然需要求导找斜率：

k=g'(x_0)=x_0^{-2}=\frac1{x_0^2}

直线过点 (x_0,b-\frac1{x_0}) 可得出直线解析式：

y=-\frac1{x_0^2}\cdot x+b-\frac2{x_0}

当 y=0，有

x_1=2x_0-bx_0^2

于是我们就可以一直迭代。

精度分析

我们要分析时间复杂度，就一定要知道它迭代一次能获得的精度。

假设我们当前的数是 x_0，有 \epsilon 的误差，那么：

bx_0 &= 1 -\epsilon\\ bx_0 - 1 &= -\epsilon\\ (bx_0 - 1)^2 &= \epsilon^2\\ b^2x_0^2-2bx_0+1&=\epsilon^2\\ b(2x_0-bx_0^2)&=1-\epsilon^2 \end{align*}

令 x_1 = 2x_0-bx_0^2 那么：

bx_1=1-\epsilon^2

当 \epsilon < 1 时我们每迭代一次误差就会减小到平方级别，也就是每次迭代精度翻倍，所以我们只需要 O(\log_2 \text{len}_a) 次就可以达到要求。

所以说它的复杂度是 T(n) = T(\frac n 2) + O(n \log n) = O(n \log n) 的，其中 n = \text{len}_a。

那么出现了小数怎么办呢？我们拿一个变量存储小数点在何处即可。不过要注意加减法需要对齐，乘法需要移动小数点。

至此，你已经学会了如何求高精度除法。（什么？你说你不会多项式求逆所以通不过板子？看看我的题解）

代码就不给了。

代码实现之类的可以看看我的帖子。还有我的高精度四则运算：从入门到入土，里面有一个常数较大的参考实现贴着时限飞过去的。