Square Root Algorithm

Here a square root algorithm is presented that yields a square root with very quick convergence. I first learned about this particular algorithm while reading The Feynman Lectures on Physics by Feynman, Leighton, and Sands which is now available for free online.

To find the square root of a number $n$, we first come up with a guess. We will call it $a_0$. The closer we can get our guess to $\sqrt{n}$, the better. Once we have our guess, we find $n/a_0$, then we compute the average of $a_0$ and $n/a_0$. That will be $a_1$.

$$a_1 = \frac{1}{2} \left( a_0 + \frac{n}{a_0} \right)$$

We just keep following that pattern to further increase accuracy as we wish. So $a_2$ will be

$$a_2 = \frac{1}{2} \left( a_1 + \frac{n}{a_1} \right).$$

As an example, I will calculate the square root of two.

To come up with a good guess, we have to consider the perfect square numbers that come before and after $2$. The perfect square before is $1$ and the one after is $4$. Consider the inequality,

$$1 < 2 < 4$$

Now take the square root of each part.

$$\sqrt{1} < \sqrt{2} < \sqrt{4}$$ $$1 < \sqrt{2} < 2$$

We see that the square root of two should be somewhere between one and two based on the above discussion. Let's pick $1.5$ as our guess and toss it into the machine.

$$n=2$$ $$a_0=1.5=\frac{3}{2}$$

Now for some arithmetic...

$$a_1 = \frac{1}{2} \left( \frac{3}{2} + \frac{2}{\frac{3}{2}} \right)$$ $$ = \frac{1}{2} \left( \frac{3}{2} + \frac{4}{3} \right)$$ $$ = \frac{1}{2} \left( \frac{9}{6} + \frac{8}{6} \right)$$ $$ = \frac{1}{2} \left( \frac{17}{6} \right)$$ $$a_1 = \frac{17}{12} = 1.416666666 \ldots = 1.41\overline{6} $$

Let's do another round!

$$a_2 = \frac{1}{2} \left( \frac{17}{12} + \frac{2}{\frac{17}{12}} \right)$$ $$ = \frac{1}{2} \left( \frac{17}{12} + \frac{24}{17} \right)$$ $$ = \frac{1}{2} \left( \frac{289}{204} + \frac{288}{204} \right)$$ $$ = \frac{1}{2} \left( \frac{577}{204} \right)$$ $$a_2 = \frac{577}{408} = 1.414\overline{2156862745098039}$$

And another!

$$a_3 = \frac{1}{2} \left( \frac{577}{408} + \frac{2}{\frac{577}{408}} \right)$$ $$ = \frac{1}{2} \left( \frac{577}{408} + \frac{816}{577} \right)$$ $$ = \frac{1}{2} \left( \frac{332929}{235416} + \frac{332928}{235416} \right)$$ $$ = \frac{1}{2} \left( \frac{665857}{235416} \right)$$ $$a_3 = \frac{665857}{470832} \approx 1.414213562374$$

The actual square root of two looks like this.

$$ \sqrt{2} = 1.41421356237309504880 \ldots$$