根号n | Fang Guojian’s Homepage

上次我们聊到 $\sqrt{2}$ ^[1]，展示了如何计算 $\sqrt{2}$ 的近似值。那么如果我们想计算任意正整数 $n$ 的平方根 $\sqrt{n}$ 呢？

在计算 $\sqrt{2}$ 的时，有一个关键的递归公式：

\sqrt{2} = 1 + \frac{1}{1+\sqrt{2}}

仔细观察，就会发现， $\sqrt{2}$ 被分成了整数部分 $1$ ，以及小数部分 $\frac{1}{1+\sqrt{2}}$ 。

如果我们把任何一个正整数 $n$ 的平方根 $\sqrt{n}$ 表示为整数和小数两个部分^[2]：

\begin{align*} \sqrt{n} = \lfloor \sqrt{n} \rfloor + \lbrace \sqrt{n} \rbrace \end{align*}

对于 $\sqrt{n}$ 如何构造这样一个等式，然后递归带入来计算呢？我们可以通过平方差公式^[3]来辅助我们：

\begin{align*} \sqrt{n} - \lfloor \sqrt{n} \rfloor &= \frac{n - {\lfloor \sqrt{n} \rfloor}^2}{\sqrt{n} + \lfloor \sqrt{n} \rfloor} \\ &= \frac{1}{\frac{\sqrt{n} + \lfloor \sqrt{n} \rfloor}{n - {\lfloor \sqrt{n} \rfloor}^2}} \tag{1} \end{align*}

对于特定的 $n$ , 虽然我们暂时还不知道 $\sqrt{n}$ 的近似值，但是 $\lfloor \sqrt{n} \rfloor$ 是可以确定的^[4]。用自己顺手的方法求解 $\lfloor \sqrt{n} \rfloor$ 就好。

我们来尝试求解 $\sqrt{19}$ 。易得， $\lfloor \sqrt{19} \rfloor = 4$ 。代入公式 $(1)$ ，

\begin{align*} \sqrt{19} - 4 &=\frac{1}{\frac{\sqrt{19} + 4}{3}} \\ &=\frac{1}{\frac{4 + \lbrace \sqrt{19} \rbrace + 4}{3}} \\ &=\frac{1}{\frac{8 + \lbrace \sqrt{19} \rbrace}{3}} \end{align*}

现在关注一下等式右边的分母部分。如果我们想要继续构造连分数，那么考虑

\begin{align*} (8+\lbrace \sqrt{19} \rbrace) / 3 &= 2 \tag{2}\\ (8+\lbrace \sqrt{19} \rbrace)\mod 3 &= 2 + \lbrace \sqrt{19} \rbrace \\ &= 2 + (\sqrt{19} - 4) \\ &= \sqrt{19} - 2 \tag{3} \end{align*}

代入等式，得到：

\begin{align*} \sqrt{19} - 4 &=\frac{1}{\frac{8 + \lbrace \sqrt{19} \rbrace}{3}} \\ &=\frac{1}{2 + \frac{\sqrt{19} - 2}{3}} \\ &=\frac{1}{2 + \frac{15}{3(\sqrt{19} + 2)}} \\ &=\frac{1}{2 + \frac{1}{\frac{\sqrt{19} + 2}{5}}} \\ &=\frac{1}{2 + \frac{1}{\frac{6 + \lbrace \sqrt{19} \rbrace}{5}}} \end{align*}

把整个计算过程中需要用到的公式统一整理一下，得到

\begin{align*} \sqrt{19} = \frac{4 + \lbrace \sqrt{19} \rbrace}{1} &= 4 + \frac{\sqrt{19} - 4}{1} &= 4 + \frac{1}{\frac{\sqrt{19} + 4}{3}} &= 4 + \frac{1}{\frac{8 + \lbrace \sqrt{19} \rbrace}{3}} \\ \frac{8 + \lbrace \sqrt{19} \rbrace}{3} &= 2 + \frac{\sqrt{19} - 2}{3} &= 2 + \frac{1}{\frac{\sqrt{19} + 2}{5}} &= 2 + \frac{1}{\frac{6 + \lbrace \sqrt{19} \rbrace}{5}} \\ \frac{6 + \lbrace \sqrt{19} \rbrace}{5} &= 1 + \frac{\sqrt{19} - 3}{5} &= 1 + \frac{1}{\frac{\sqrt{19} + 3}{2}} &= 1 + \frac{1}{\frac{7 + \lbrace \sqrt{19} \rbrace}{2}} \\ \frac{7 + \lbrace \sqrt{19} \rbrace}{2} &= 3 + \frac{\sqrt{19} - 3}{2} &= 3 + \frac{1}{\frac{\sqrt{19} + 3}{5}} &= 3 + \frac{1}{\frac{7 + \lbrace \sqrt{19} \rbrace}{5}} \\ \frac{7 + \lbrace \sqrt{19} \rbrace}{5} &= 1 + \frac{\sqrt{19} - 2}{5} &= 1 + \frac{1}{\frac{\sqrt{19} + 2}{3}} &= 1 + \frac{1}{\frac{6 + \lbrace \sqrt{19} \rbrace}{3}} \\ \frac{6 + \lbrace \sqrt{19} \rbrace}{3} &= 2 + \frac{\sqrt{19} - 4}{3} &= 2 + \frac{1}{\frac{\sqrt{19} + 4}{1}} &= 2 + \frac{1}{\frac{8 + \lbrace \sqrt{19} \rbrace}{1}} \\ \frac{8 + \lbrace \sqrt{19} \rbrace}{1} &= 8 + \frac{\sqrt{19} - 4}{1} &= 8 + \frac{1}{\frac{\sqrt{19} + 4}{3}} &= 8 + \frac{1}{\frac{8 + \lbrace \sqrt{19} \rbrace}{3}} \\ \dots \end{align*}

所以^[5]，

\sqrt{19} = [4;2,1,3,1,2,8,2,1,3,1,2,8,...]

上一篇文档提到的几个问题，也附上简短的回答。如有任何不准确的地方，还请多多包涵。

为什么可以用一个等式替换到自身中？这样的做法正确吗？

一个等式替换到自身中，这其实就是递归的定义。
对于其他开根号的数，如 $\sqrt{3}$ ，如何构造一个类似 $\sqrt{2}$ 的等式？

本文即是答案。
连分数展开的形式，似乎和迭代法求最大公约数很像，他们有什么关系？

迭代法求最大公约数，实际上就是将两个数不断用更小的数去拆分更大的数。在连分数中，实际上也是以类似的方式在运作，如上公式 $(2),(3)$ 。