Square Root of n | Fang Guojian’s Homepage

Preparation

Last time we talked about $\sqrt{2}$ ^[1] and demonstrated how to calculate the approximate value of $\sqrt{2}$ . So what if we want to calculate the square root $\sqrt{n}$ of any positive integer $n$ ?

When calculating $\sqrt{2}$ , there was a key recursive formula:

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

Careful observation will reveal that $\sqrt{2}$ is divided into an integer part $1$ and a fractional part $\frac{1}{1+\sqrt{2}}$ .

If we represent the square root $\sqrt{n}$ of any positive integer $n$ as both an integer and a fractional part^[2]:

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

How can we construct such an equation for $\sqrt{n}$ and then recursively substitute it to calculate? We can use the difference of squares formula^[3] to assist us:

\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*}

For a specific $n$ , although we do not yet know the approximate value of $\sqrt{n}$ , $\lfloor \sqrt{n} \rfloor$ can be determined^[4]. Use your preferred method to solve for $\lfloor \sqrt{n} \rfloor$ .

Solution

Let's try to solve $\sqrt{19}$ . It is easy to find that $\lfloor \sqrt{19} \rfloor = 4$ . Substituting into formula (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*}

Now focus on the denominator part on the right side of the equation. If we want to continue constructing a continued fraction, then consider

\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*}

Substituting into the equation, we get:

\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*}

Collecting all the formulas needed in the entire calculation process, we get

\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*}

So^[5],

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

Q&A

Here are brief answers to some of the questions mentioned in the previous article. If there are any inaccuracies, please bear with me.

Why can an equation be substituted into itself? Is this method correct?

Replacing an equation into itself is essentially the definition of recursion.
For other square root numbers, like $\sqrt{3}$ , how can we construct an equation that is similar to the equation for calculating $\sqrt{2}$ ?

This article is the answer.
The form of the continued fraction seems similar to the iterative method for finding the greatest common divisor. What is their relationship?

The iterative method for finding the greatest common divisor essentially breaks down two numbers using smaller numbers continuously. In continued fractions, a similar mechanism operates, as shown in formulas (2) and (3).