开平方的算法

hbghlyj

en.wikipedia.org/wiki/Methods_of_computing_square_roots
pcjohnson.net/312/Sqrt.pdf
pcjohnson.net/312/SqrtPresentation.pdf

1 Greek Method

$\forall a \in \mathbb{Q}$ such that $a>1$, the sequences $\left\{a_{n}\right\}$ and $\left\{b_{n}\right\}$ both converge to $\sqrt{a}$ when defined as:
\begin{aligned}
&a_{i}=a \\
&b_{i}=1 \\
&a_{n+1}=\frac{a_{n}+b_{n}}{2} \\
&b_{n+1}=\frac{2 a_{n} b_{n}}{a_{n}+b_{n}}
\end{aligned}

1.1 The Product is Always $a$

$$\forall n \in \mathbb{N}, a_{n} b_{n}=a$$Base Case for Proof by Induction
$n=1$:  $a_{1} b_{1}=a \times 1=a$
Induction Step
Assume $a_{k} b_{k}=a$, then
$a_{k+1} b_{k+1}=\left(\frac{a_{k}+b_{k}}{2}\right)\left(\frac{2 a_{k} b_{k}}{a_{k}+b_{k}}\right)=a_{k} b_{k}=a$

1.2 $a_{n}$ is Always Greater Than $b_{n}$

$$\forall n \in \mathbb{N}, a_{n} \geq b_{n}$$\begin{gathered}
\left(a_{k}-b_{k}\right)^{2}>0 \\
a_{k}^{2}-2 a_{k} b_{k}+b_{k}^{2}>0 \\
a_{k}^{2}+2 a_{k} b_{k}+b_{k}^{2}>4 a_{k} b_{k} \\
\left(a_{k}+b_{k}\right)^{2}>4 a b_{k} \\
\frac{a_{k}+b_{k}}{2}>\frac{2 a_{k} b_{k}}{a_{k}+b_{k}} \\
a_{k+1}>b_{k+1}
\end{gathered}

1.3 $\left\{a_{n}\right\}$ are $\left\{b_{n}\right\}$ Monotone

$\left\{a_{n}\right\}$ is Strictly Decreasing
Since $a_{n}>b_{n} \forall n \in \mathbb{N}$ :
\begin{gathered}
a_{n}>b_{n}\\
2 a_{n}>a_{n}+b_{n}\\
a_{n}>\frac{a_{n}+b_{n}}{2}\\
a_{n}>a_{n+1}
\end{gathered}
$\left\{b_{n}\right\}$ is Strictly Increasing
Since $a_{n}>b_{n} \forall n \in \mathbb{N}$ :
\begin{gathered}
b_{n}<a_{n} \\
b_{n}^{2}<a_{n} b_{n} \\
a_{n} b_{n}+b_{n}^{2}<2 a_{n} b_{n} \\
b_{n}\left(a_{n}+b_{n}\right)<2 a_{n} b_{n}\\
b_{n}<\frac{2 a_{n} b_{n}}{a_{n}+b_{n}} \\ b_{n}<b_{n+1}
\end{gathered}

1.4 $\left\{a_{n}\right\}$ and $\left\{b_{n}\right\}$ are Cauchy

We know $a_{n}>b_{n}$ and $a_{n} b_{n}=a$, so:
\begin{gathered}
a_{n}>b_{n} \\
a_{n}>\frac{a}{a_{n}} \\
a_{n}^{2}>a \\
a_{n}>\sqrt{a}
\end{gathered}Similarly, $b_{n}<\sqrt{a}$ for all $n$. Thus $\left\{a_{n}\right\}$ is monotone decreasing and bounded below and $\left\{b_{n}\right\}$ is monotone increasing and bounded above. Both sequences must be Cauchy, and since $\mathbb{R}$ is complete, both sequences must converge.

1.5 $\left\{a_{n}\right\}$ and $\left\{b_{n}\right\}$ Converge to $\sqrt{a}$

$\left\{a_{n}^{2}\right\}$ Converges to $a$
Since $\left\{a_{n}\right\}$ is a Cauchy sequence, $\forall \varepsilon>0, \exists N_{1} \in \mathbb{N}$ such that $\forall n, m>N_{1},\left|a_{n}-a_{m}\right|<\frac{1}{2 a} \varepsilon$. Also, $\left\{a_{n}\right\}$ is strictly decreasing, so if $m>n, a_{m}<a_{n}$ and therefore $\left|a_{n}-a_{m}\right|=a_{n}-a_{m}$. From this:
\begin{aligned}
\frac{1}{2 a} \varepsilon &>a_{n}-a_{n+1} \\
\frac{1}{2 a} \varepsilon &>a_{n}-\frac{a_{n}+b_{n}}{2} \\
\frac{1}{2 a} \varepsilon &>\frac{2 a_{n}}{2}-\frac{a_{n}+\frac{a}{a_{n}}}{2} \\
\frac{1}{2 a} \varepsilon &>\frac{a_n-\frac{a}{a_{n}}}{2} \\
\varepsilon &>a\left(a_n-\frac{a}{a_{n}}\right) \\
\varepsilon &>\frac{a}{a_{n}}\left(a_{n}^2-a\right) \\
\lim _{n \rightarrow \infty} a_{n}^{2} &=a
\end{aligned}
$\left\{b_{n}^{2}\right\}$ Converges to $a$
Since $\left\{b_{n}\right\}$ is a Cauchy sequence, $\forall \varepsilon>0, \exists N_{2} \in \mathbb{N}$ such that $\forall n, m>N_{2},\left|b_{n}-b_{m}\right|<\varepsilon$. Also, $\left\{b_{n}\right\}$ is strictly increasing, so if $m>n, b_{m}>b_{n}$ and therefore $\left|b_{n}-b_{m}\right|=b_{m}-b_{n}$. From this:
\begin{aligned}
\varepsilon &>b_{n+1}-b_{n} \\
\varepsilon &>\frac{2 a_{n} b_{n}}{a_{n}+b_{n}}-b_{n} \\
\varepsilon &>\frac{2 \frac{a}{b_{n}} b_{n}}{\frac{a}{b_{n}}+b_{n}}-b_{n} \\
\varepsilon &>\frac{2 a b_{n}}{a+b_{n}^{2}}-\frac{\left(a+b_{n}^{2}\right) b_{n}}{a+b_{n}^{2}} \\
\varepsilon &>\frac{\left(a-b_{n}^{2}\right) b_{n}}{a+b_{n}^{2}}
\end{aligned}Since $b_{n}$ is increasing and bounded above, it does not converge to zero nor does $b_{n}^{2}$ diverge to infinity. Also, $a$ is constant so $\left(a-b_{n}^{2}\right)$ must converge to zero, which means:
$$\lim _{n \rightarrow \infty} b_{n}^{2}=a$$
$\left\{a_{n}\right\}$ and $\left\{b_{n}\right\}$ Converge to $\sqrt{a}$
Since $\lim _{n \rightarrow \infty} a_{n}^{2}=\lim _{n \rightarrow \infty} b_{n}^{2}=a$, we have shown that the squares of both sequences converge to $a$, and thus each sequence must converge to $\sqrt{a}$.

1.6 Alternate Proof that $\lim _{n \rightarrow \infty} a_{n}=\lim _{n \rightarrow \infty} b_{n}=\sqrt{a}$

Since $\left\{a_{n}\right\}$ is a Cauchy sequence, $\forall \varepsilon>0, \exists N \in \mathbb{N}$ such that $\forall n, m>N,\left|a_{n}-a_{m}\right|<\frac{1}{2} \varepsilon$. The sequence $\left\{a_{n}\right\}$ is monotone decreasing so if $m>n, a_{m}<a_{n}$ and therefore $\left|a_{n}-a_{m}\right|=a_{n}-a_{m}$. Thus:\begin{aligned}
\frac{1}{2} \varepsilon &>a_{n}-a_{n+1} \\
\frac{1}{2} \varepsilon &>a_{n}-\frac{a_{n}+b_{n}}{2} \\
\varepsilon &>a_{n}-b_{n} \\
\lim _{n \rightarrow \infty} a_{n} &=\lim _{n \rightarrow \infty} b_{n}
\end{aligned}Since $\lim _{n \rightarrow \infty} a_{n}=\lim _{n \rightarrow \infty} b_{n}$, and $a_{n} b_{n}=a$,
\begin{gathered}
\lim _{n \rightarrow \infty} a_{n}^{2}=\lim _{n \rightarrow \infty} b_{n}^{2}=\lim _{n \rightarrow \infty} a_{n} b_{n}=a \\
\lim _{n \rightarrow \infty} a_{n}=\lim _{n \rightarrow \infty} b_{n}=\sqrt{a}
\end{gathered}

hbghlyj

2 Newton's Method 1

Newton's method for finding the square root of $a$ is to begin by making an initial guess $b_{1}$ such that $1 \leq b_{1} \leq a$. Ideally, $b_{1}$ will be the integer nearest $a$, but initial proximity only reduces the number of iterations necessary to achieve the desired accuracy. Dividing $a$ by $b_{1}$ and averaging the quotient with $b_{n}$ will result in a better approximation for $\sqrt{a}$. This is repeated until the desired accuracy is achieved. To state the algorithm as a recursive sequence, $$ b_{n+1}=\frac{b_{n}+\frac{a}{b_{n}}}{2} $$ To prove that the algorithm works, it shall first be shown that it works for the trivial case where the initial guess, $b_{1}$, is equal to $\sqrt{a}$. Then a full proof for any value of $b_{1}$ such that $1 \leq b_{1} \leq \sqrt{a}$ shall be provided.

2.1 $b_{1}=\sqrt{a}$

Since the algorithm allows any initial guess between one and $a$, it is possible that $b_{1}$ is equal to the square root of $a$. In this trivial case, each term of the sequence is identically $\sqrt{a}$ as shown by starting with $b_{k}=\sqrt{a}$ : $$ b_{k+1}=\frac{b_{k}+\frac{a}{b_{k}}}{2}=\frac{\sqrt{a}+\frac{a}{\sqrt{a}}}{2}=\frac{\sqrt{a}+\sqrt{a}}{2}=\sqrt{a} $$ Since $b_{1}=\sqrt{a}, b_{n}=\sqrt{a} \forall n \in \mathbb{N}$ by induction. Incidentally, this is the only case where any terms of the sequence will equal $\sqrt{a}$.

2.2 The Tail of $\left\{b_{n}\right\}$ is Bounded Below

For most initial guesses, $b_{1}$ will not be equal to $\sqrt{a}$ and it must be shown that $\left\{b_{n}\right\}$ converges to $\sqrt{a}$. In this case we can let $\delta_{n}=\sqrt{a}-b_{n}$. For any $b_{n}$, we have: \begin{aligned} \delta_{n}^{2} &\geq 0\\ a-2 \sqrt{a}\delta_{n}+\delta_{n}^{2}+a &\geq 2a-2 \sqrt{a}\delta_{n}\\ \left(\sqrt{a}-\delta_{n}\right)^{2}+a &\geq 2 \sqrt{a}\left(\sqrt{a}-\delta_{n}\right)\\ b_n^2+a&≥2b_n\sqrt a\\ (∵b_n>0)\qquad\frac{b_{n}+\frac{a}{b_{n}}}{2} & \geq \sqrt{a} \\ b_{n+1} & \geq \sqrt{a} \end{aligned} Thus if we ignore the first term, the tail of the sequence is bounded below by $\sqrt{a}$. From this $\frac{a}{b_{n}}$ must be bounded above by $\sqrt{a}$ for all $n>1$: \begin{aligned} b_{n} & \geq \sqrt{a} \implies&\sqrt{a} \geq \frac{a}{b_{n}} \end{aligned}

2.3 The Tail of $\left\{b_{n}\right\}$ is Monotone Decreasing

Next, it shall be shown that this tail is decreasing. Since $b_{n} \geq \sqrt{a} \geq \frac{a}{b_{n}} \forall n>1$, \begin{aligned} b_{n} & \geq \frac{a}{b_{n}} \\ 2 b_{n} & \geq b_{n}+\frac{a}{b_{n}} \\ b_{n} & \geq \frac{b_{n}+\frac{a}{b_{n}}}{2} \\ b_{n} & \geq b_{n+1} \end{aligned}

2.4 $\left\{b_{n}\right\}$ Converges to $\sqrt{a}$

Since the tail of $\left\{b_{n}\right\}$ is bounded below and monotone decreasing, it is a Cauchy sequence and $\forall \varepsilon>0, \exists N \in \mathbb{N}$ such that $\forall n, m>N,\left|b_{n}-b_{m}\right|<\frac{1}{2 a} \varepsilon$. Also, if $m>n$, then $b_{m}< b_{n}$ and therefore $\left|b_{n}-b_{m}\right|=b_{n}-b_{m}$. Finally, $a_{n} / b_{n} \geq 1 \forall n$, so: \begin{aligned} \frac{1}{2 a} \varepsilon & \geq b_{n}-b_{n+1} \\ \frac{1}{2 a} \varepsilon & \geq \frac{2 b_{n}}{2}-\frac{b_{n}+\frac{a}{b_{n}}}{2} \\ \frac{1}{2 a} \varepsilon & \geq \frac{b_{n}-\frac{a}{b_{n}}}{2} \\ \varepsilon & \geq a\left(b_{n}-\frac{a}{b_{n}}\right) \\ \varepsilon & \geq \frac{a}{b_{n}}\left(b_{n}^{2}-a\right) \geq b_{n}^{2}-a \\ \varepsilon & \geq b_{n}^{2}-a \\ \lim _{n \rightarrow \infty} b_{n}^{2} &=a \\ \lim _{n \rightarrow \infty} b_{n} &=\sqrt{a} \\\left\{b_{n}\right\} & \rightarrow \sqrt{a} \end{aligned}

---

¹ Also known as the Babylonian method or Heron's method

hbghlyj

3 Bahkshali Method

The Bahkshali formula was originally written to give the approximate square root as a single expression, although iteration is possible. As originally presented, $$ \sqrt{a}=\sqrt{b^{2}+d} \approx b+\frac{d}{2 b}-\frac{(d / 2 b)^{2}}{2\left(b+\frac{d}{2 b}\right)} $$ To find $\sqrt{a}$, one must first guess at $b$ and then determine $d$ by the relation $d=a-b^{2}$. The approximate square root is then given by the formula. The result from the approximation can be used as $b$ for a subsequent iteration.

3.1 Sequential Form

To iterate for a more accurate solution, a sequence can be defined as: \begin{aligned} d_{n} &=a-b_{n}^{2} \\ b_{n+1} &=b_{n}+\frac{d_{n}}{2 b_{n}}-\frac{\left(\frac{d_{n}}{2 b_{n}}\right)^{2}}{2\left(b_{n}+\frac{d_{n}}{2 b_{n}}\right)} \end{aligned} Rewriting the sequence in terms of only $a$ and $b_{n}$, we have:\begin{aligned} b_{n+1} =&b_{n}+\frac{d_{n}}{2 b_{n}}-\frac{\left(\frac{d_{n}}{2 b_{n}}\right)^{2}}{2\left(b_{n}+\frac{d_{n}}{2 b_{n}}\right)} \\ =&b_{n}+\frac{d_{n}}{2 b_{n}}-\frac{d_{n}^{2}}{8 b_{n}^{3}+4 b_{n} d_{n}} \\ =&b_{n}+\frac{a-b_{n}^{2}}{2 b_{n}}-\frac{\left(a-b_{n}^{2}\right)^{2}}{8 b_{n}^{3}+4 b_{n}\left(a-b_{n}^{2}\right)} \\=& b_{n}+\frac{a-b_{n}^{2}}{2 b_{n}}-\frac{a^{2}-2 a b_{n}^{2}+b_{n}^{4}}{4 b_{n}^{3}+4 a b_{n}} \\=& b_{n}+\frac{a-b_{n}^{2}}{2 b_{n}}-\frac{a^{2}-2 a b_{n}^{2}+b_{n}^{4}}{4 b_{n}\left(b_{n}^{2}+a\right)} \\=& \frac{4 b_{n}^{2}\left(b_{n}^{2}+a\right)+2\left(a-b_{n}^{2}\right)\left(b_{n}^{2}+a\right)-\left(a-b_{n}^{2}\right)^{2}}{4 b_{n}^{3}+4 a b_{n}} \\=& \frac{a^{2}+6 a b_{n}^{2}+b_{n}^{4}}{4 b_{n}^{3}+4 a b_{n}} \end{aligned} This form of the equation might not be as elegant, but being in standard form makes it simpler to find an equivalent expression.

3.2 Newton's Method Revisited

\begin{aligned} b_{n+2} &=\frac{b_{n+1}+a / b_{n+1}}{2}=\frac{\frac{b_{n}+a / b_{n}}{2}+\frac{a}{\frac{b_{n}+a / b_{n}}{2}}}{2} \\ &=\frac{b_{n}+a / b_{n}+\frac{4 a}{b_{n}+a / b_{n}}}{4} \\ &=\frac{b_{n}}{4}+\frac{a}{4 b_{n}}+\frac{a b_{n}}{b_{n}^{2}+a} \\ &=\frac{b_{n}^{2}\left(b_{n}^{2}+a\right)+a\left(b_{n}^{2}+a\right)+4 a b_{n}^{2}}{4 b_{n}\left(b_{n}^{2}+a\right)} \\ b_{n+2} &=\frac{a^{2}+6 a b_{n}^{2}+b_{n}^{4}}{4 b_{n}^{3}+4 a b_{n}} \end{aligned} The unexpected result shown here is that the Bahkshali formula is equivalent to two iterations of Newton's method. As it has been shown that Newton's method converges to the square root, it is clear that the Bahkshali method will also converge.

3.3 Efficiency

The similarity to Newton's method makes this an ineffective algorigthm for computers, which can perform simple operations very quickly. A single iteration of the Bahkshali method requires a larger stack and more operations than two iterations of Newton's method, which is algebraically identical. The functionality of the formula is in the repetition of the terms $\frac{d}{2 b}$ and $b+\frac{d}{2 b}$. This makes it convenient for hand calculations, where this repetition can save a substantial amount of time. Provided a reasonable first guess, the Bahkshali formula provides a very accurate approximation, as shown in the following table. For creating the chart, $b$ was taken as the floor function of the square root.