笔算开平方

---

一、算法流程

（1）设要开方的数为 $A$，将 $A$ 的数字两两分组，从左到右记为 $A_{1},A_{2},\ldots$，例如

$\begin{aligned}758693 &\Rightarrow 75'86'93 \\ 78965 &\Rightarrow 7'89'65\end{aligned}$

在第一个例子中，

$A_{1}=75,A_{2}=86,A_{3}=93$

在第二个例子中，

$A_{1}=7,A_{2}=89,A_{3}=65$

为了计算方便，接下来的过程中以 $A=75'86$ 为例

（2）将第一位开方：即计算满足 $x_{1}^2\leq A_1$ 的最大的 $x_{1}$

$x_{1}^2\leq 75\Rightarrow \max\{x_{1}\}=8$

然后将 $x_{1}^2$，也就是 $64$ 写下来，相减抄下去

（3）我们知道，对于普通的除法，接下来的操作是下移一位，但在开平方中，我们需要下移两位，然后将当前商乘以 $20$，计算满足 $(20x_1+x_2)x_2\leq A_2$ 的最大的 $x_{2}$，显然 $x_{2}<10$

$(160+x_{2})x_{2}\leq 1168\Rightarrow \max\{x_{2}\}=6$

将 $(20x_{1}+x_{2})x_{2}$ 的结果写下来相减，如图所示：

（4）重复（3）过程即可，只要你想，你可以不断开下去，当然你可能发现了，越往后计算越复杂

---

二、算法原理

我们假设开方的结果是

$P=\sum_{i=0}^{n}10^i x_{i}$

那么我们尝试把 $P$ 平方，即

$P^2=\sum_{i=0}^{n} (10^{2i} x_{i}^{2}+ 2\times 10^{i} x_{i} \sum_{j=i+1}^{n}10^{j} x_{j} )$

$P^2=\sum_{i=0}^{n} 10^i x_{i}(10^i x_{i} + 2 \sum_{j=i+1}^{n}10^{j} x_{j} )$

接下来我们考虑各项的意义：

（1）$10^i x_{i}$ 项就是商中当前正在计算的位置的数

（2）$2 \sum_{j=i+1}^{n}10^j x_{j}$ 就是当前位前面的位的累加和乘以 $2$ 的结果

我们的思想是逐位确定

首先确定第一位，方法是显然的

然后假设后面的位都是 $0$，然后按照上面的式子求解最小的符合条件的当前位的值

这样不断地逐位进行确定就可以实现笔算开平方