Cooking Up Your OWN Square Roots at Home

Some readers of the blog reached out to me about the post of the square-root. They pointed out I forgot that I forgot to introduce a famous ancient idea to approximate any square root $\sqrt{S}$.

The first explicit algorithm for approximating is known as Heron's method. The method is named after the first-century Greek mathematician Hero of Alexandria who described the method in his work Metrica. This method is also called the Babylonian method but although there is no evidence that the method was known to Babylonians. In addition, the method is not to be confused with the Babylonian method for approximating hypotenuses which is also a way of approximating roots. However, Heron’s method is a pretty neat trick to approximate the square root with astonishing precision. For a very old idea it works very well.

The idea of Hero of Alexandria is actually pretty elegant. Assume you have a rectangle with sides of length $a$ and $b$ and an area of $S$. Then you can just choose a side $a$ and then $b$ cannot have any other value than $\frac{S}{a}$ because otherwise the rectangle would not have area $S$. If $a < \sqrt{S}$ then the other side $b$ will be larger than $\sqrt{S}$ as $\sqrt{S} < b = \frac{S}{a}$. So one side is undershooting the square root, while the other side is overshooting it. What do we do? Average them. $$ a_{\text{new}} = \tfrac{1}{2}\Big(a + \tfrac{S}{a}\Big)$$ This new $a_{\text{new}}$ is somewhere between the two, and much closer to the true square root. Now you repeat the trick, each time replacing $a$ by this average. Step by step, the rectangle reshapes itself into a square with sides very close to $\sqrt{S}$. This means that both $a$ and $b$ will approximate $\sqrt{S}$ after some iterations. The idea is illustrated below with a video where the method is applied on $S=16$.

The concept of averaging out these two sides will eventually lead to a better and better approximation of the square root $\sqrt{S}$ by effectively balancing the size of the lengths. The iteration formula In modern terms, we start with a guess $x_0>0$, and then update by $$ x_{n+1} = \frac{1}{2}\Big(x_n + \frac{S}{x_n}\Big). $$ That’s all there is to it! Then for a large number of iterations $x_n$ converges to $\sqrt{S}$. Using our limit notation introduced in last post, we can also express it as $$ \lim_{n \to \infty} x_n = \sqrt{S}.$$ What’s magical is how fast it works. Each step roughly doubles the number of correct digits in the approximation. So even in ancient times, a couple of iterations were enough to compute square roots to remarkable precision without a calculator. However, there is much more to this idea. What we are describing here is actually Newton's method. These hidden aspects became apparent after the discovery of calculus. However, once again, that’s something for a future blogpost.