Calculating the square root of 2

Calculating the square root of a number is one of the first problems tackled with numerical methods, known I think to the ancient Babylonians. The observation is that if $x,\,y>0$ and $y\ne\sqrt{x}$ then $y,\,x/y$ will be on opposite sides of $\sqrt{x}$, and we could try averaging them. So try $y_0=1,\,y_{n+1}=\frac12\left(y_n+\frac{x}{y_n}\right)$. This is actually the Newton-Raphson method 5xum mentioned. The number of correct decimal places approximately doubles at each stage, i.e. you probably only have to go as far as $y_5$ or so.

Here's the way I learnt to obtain decimal digit after decimal digit when I began middle school:

\begin{array}{lcl} 2&\big( &\color{red}1.414\,2\dots \\[1ex] 1\,00&& 24\times \color{red}4=96<100\\ -96\,&& 25\times5=125>100\\[1ex] \phantom{-0}4\,00&&281\times\color{red}1<400\\ \;\:-2\,81&&282\times2>400\\[1ex] \phantom{-0}119\,00&&2824\times\color{red}4<11900\\ \phantom{0}{-}112\,96&&2825\times5>11900 \\[1ex] \phantom{00\;}604\,00&&28282\times\color{red}2 < 60400 \\ &&28283\times3> 60400 \end{array} &c.

Let me explain the procedure on the first two steps. It relies on a clever use of the identity $(x+y)^2=x^2+2xy+y^2$. Suppose more generally we want to find the square root of a number $a$.

1. We first find the greatest natural number $n$ such that $n^2\le a$.
2. If $a$ is not a perfect square, i.e. if $n^2<a$, let $d$ be the first decimal digit of the square root. This is the greatest digit such that $\;\Bigl(n+\frac d{10}\Bigr)^2\le a$. We'll transform this inequality into a more easy-to-use test: \begin{align} \Bigl(n+\frac d{10}\Bigr)^2\le a&\iff \frac{2n}{10}d+\frac{d^2}{100}<a -n^2\\ &\iff (10\times 2n+d)\times d\le (a-n^2)\times 100 \end{align} In practice, this means, we calculate the difference $a-n^2$ and add two 0s. Then we double $n$, add a digit d (this is the result of calculating $10\times 2n+d$) and multiply what we obtain by this digit. Last, we test whether the result is less than $100(a-n^2)$, and retain the largest possible digit.

On a similar note to the answer by R. Romero: in the special case of taking the square root of an integer $N$, it is fairly straightforward to calculate the continued fraction representation of $\sqrt{N}$.

In the particular case $N=2$, we have: $$ \sqrt{2} = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \ddots}}}. $$ (This follows from the fact that if $x = \sqrt{2}-1$, then $x = \sqrt{2}-1 = \frac{1}{\sqrt{2}+1} = \frac{1}{2+x}$.)

Now, from this we can calculate subsequent rational approximations to $\sqrt{2}$:

$$ \begin{matrix} & & 1 & 2 & 2 & 2 & 2 & 2 & \cdots \\ 0 & 1 & 1 & 3 & 7 & 17 & 41 & 99 & \cdots \\ 1 & 0 & 1 & 2 & 5 & 12 & 29 & 70 & \cdots \end{matrix} $$ So, for example $\frac{99}{70} \approx 1.4142857$ whereas $\sqrt{2} \approx 1.4142136$.

(It also happens that this procedure generates solutions to Pell's equation $a^2 - 2 b^2 = \pm 1$; for example, $99^2 - 2 \cdot 70^2 = 1$. The connection is: if $a^2 - 2 b^2 = \pm 1$ then $a - b \sqrt{2} = \pm \frac{1}{a + b \sqrt{2}}$; so if $a$ and $b$ are large positive integers satisfying Pell's equation, then $a - b\sqrt{2} \approx \pm\frac{1}{2a}$ which implies $\frac{a}{b} - \sqrt{2} \approx \pm\frac{1}{2ab} \approx \pm\frac{1}{a^2\sqrt{2}}$.)