几种开平方的计算方法
10Al
·
2023-01-21 16:23:22
·
个人记录
前言
本文介绍了几种根号的近似计算方法。
在下文中，不妨假设我们已经得到了 \sqrt N 的一个估计值 S. 定义 d=N-S^2, f(x)=(S^2+x)^{1/2}. 则我们事实上就是在寻找 f(d) 的近似计算方法.
接下来，我们将按照方法所依据的基本原理分类，依次介绍四种计算方法。
泰勒公式
由泰勒公式，f(d)=f(0)+f'(0)d+f''(\xi)\dfrac{d^2}{2!}=S+\dfrac{d}{2S}-\dfrac{d^2}{8(S^2+\xi)^{3/2}}, 其中 \xi 在 0 与 d 之间。忽略余项，我们便有 \sqrt{N}\approx S+\dfrac{d}{2S}=\dfrac{N}{2S}+\dfrac{S}{2}
这个式子具有的意义是显然的。通过这个式子得到结果也是简单高效的。通过余项分析，或者直接运用基本不等式，我们也容易得到，该方法获取的近似值总比准确值大。
由于对 f(x) 使用的是线性近似，我们得到的结果和（思路上更加自然的）牛顿迭代法是一样的。出于对文章总体思想一致性的考虑，我并没有使用这种角度来分析这种算法。但我会把这种角度的分析放在末尾。
帕德近似
考虑将 f(x) 近似成两多项式函数 P(x), Q(x) 的商，即一有理函数 H(x)=\dfrac{P(x)}{Q(x)}.
一种基于分式线性递推数列的计算方法
令 S_{n+1} = \dfrac{S_n+N}{S_n+1}. 于是有 \lim_{n\to \infty} S_n=\sqrt N. （原理见浅谈分式递推数列）
一种基于连分数的计算方法
效率甚至高于牛顿迭代？
由平方差公式容易得到， \sqrt{N}-S_0=\dfrac{d}{\sqrt{N}+S_0}, 于是有 \sqrt{N}=S_0+\dfrac{d}{S_0+\sqrt{N}}=S_0+\dfrac{d}{2S_0+\frac{d}{2S_0+\dots}} 当我们在一定层数截断这个连分数，并用 S_0 来近似 \sqrt{N}, 我们便有了不同精度的 \sqrt{N} 的近似。
前三层近似分别为 \sqrt{N}\approx S_0+\dfrac{d}{2S_0}=\dfrac{2S_0^2+d}{2S_0}, \sqrt{N}\approx S_0+\dfrac{d}{2S_0+\frac{d}{2S_0}}=\dfrac{4S_0^3+3S_0d}{4S_0^2+d}, \sqrt{N}\approx S_0+\dfrac{d}{2S_0+\frac{d}{2S_0+d/2S_0}}=\dfrac{8S_n^4+8S_n^2d+d^2}{8S_n^3+4Sd^2}.经过观察，我们可以得到，记第 n 层近似所得到的最终结果的分子为 a_n, 分母为 b_n, 那么有 a_n=2S_0a_{n-1}+da_{n-2}, b_n = 2S_0b_{n-1}+db_{n-2}. 于是我们又有
### Bakhshali's method
由于是在wiki上看到的，也没有搜到中文资料，所以不知道中文名叫什么。具体来讲，我们定义 $a_n=\dfrac{1}{2}(\dfrac{N}{S_n}-S_n)$, $S_{n+1}=S_n+a_n-\dfrac{a_n^2}{2(S_n+a_n)}$. 由于缺乏资料，我不知道古人是如何得到这个式子的。但是我们将 $a_n$ 表示为 $\dfrac{d}{2S_n}$ 并加以化简，会发现这事实上即为 $S_{n+1}=\dfrac{8S_n^4+8S_n^2d+d^2}{8S_n^3+4Sd^2}$, 与我们连分数法中所得到的第三层近似一致。
### 各方法的比较
我们将假设三种应用场景，并分别对比各方法的效率。
第一种场景：高精度计算。我们选择计算 $\sqrt{23}$ 到小数点后50位。由[计算器](https://keisan.casio.com/exec/system/1273502518)得，其值约为`4.7958315233127195415974380641626939199967070419041`.
第二种场景：精度要求不高的多数据运算
第三种场景：精度要求不高的手算
附：
$\sqrt{N}$ 即为函数 $x^2-N$ 的零点。我们可以采用广为人知的牛顿迭代法，即切线近似法，由 $S_{n+1} = S_n-\dfrac{f(S_n)}{f'(S_n)}$ 得到（通常是）更精确的零点值。化简之后，我们有 $S_{n+1}=\dfrac{S_n+N/S_n}{2}$ .