Estimating square roots in your head

Imagine we want to compute the square root of a number $n$n. The basic idea of
Heron’s
method,
named after the mathematician and engineer, Heron of
Alexandria, is to find a number $g$g that is close to $sqrt{n}$n​ and to then
average that with the number $n/g$n/g, which corrects for the fact that $g$g either
over- or underestimates $sqrt{n}$n​.

I like this algorithm because it is simple and works surprisingly
well. However, I first learned about it in (Benjamin & Shermer, 2006), which
did not provide a particularly deep explanation or analysis for why this method works. The goal of this post is to better
understand Heron’s method. How does it work? Why does it work? And how good are
the estimates?

The algorithm

Let’s demonstrate the method with an example. Consider computing the square root of $n=33$n=33. We start by finding a number that forms a perfect square that is
close to $33$33. Here, let’s pick $g=6$g=6, since $6^2 = 36$62=36. Then we compute a
second number, $b = n/g$b=n/g. In practice, computing $b$b in your head may require an approximation. Here, we can compute
it exactly as $33 / 6 = 5.5$33/6=5.5. Then our final guess is the average of these two numbers or

$sqrt{n} approx frac{g+b}{2}, tag{1}$n​≈2g+b​,(1)

which in our example is

$sqrt{33} = 5.74456264654… approx frac{6 + 5.5}{2} = 5.75. tag{2}$33​=5.74456264654...≈26+5.5​=5.75.(2)

That is pretty good. The relative error is less than $0.1$0.1%! And
furthermore, this is pretty straightforward to do in your head when $n$n isn’t
too large.

Why does this work?

Intuitively, Heron’s method works because $g$g is either an over- or
underestimate of $sqrt{n}$n​. Then $n/g$n/g is an under- or overestimate,
respectively, of $sqrt{n}$n​. So the average of $g$g and $n/g$n/g should be closer to
$sqrt{n}$n​ than either $g$g or $n/g$n/g is.

While this was probably Heron’s reasoning, we can offer a better explanation
using calculus: Heron’s method works because we’re performing a second-order Taylor
approximation around our initial guess. Put more specifically, we’re making a linear approximation of the nonlinear square root function at the point
$g^2$g2.

To see this, recall that the general form of a Taylor expansion about a
point $a$a is

$f(x) = f(a) + sum_{k=1}^{infty} frac{f^{(k)}(a)(x-a)^k}{k!}, tag{3}$f(x)=f(a)+k=1∑∞​k!f(k)(a)(x−a)k​,(3)

where the notation $f^{(k)}$f(k) denotes the $k$k-th derivative of $f$f. If we define $f(x) = sqrt{x}$f(x)=x​, then

$f^{prime}(x) = frac{1}{2 sqrt{x}}, tag{4}$f′(x)=2x​1​,(4)

and so the second-order Taylor approximation of $sqrt{x}$x​ is

$sqrt{x} approx sqrt{a} + frac{x-a}{2 sqrt{a}}. tag{5}$x​≈a​+2a​x−a​.(5)

Now choose $x=n$x=n, and let $h(x)$h(x) denote the Taylor expansion around $a = g^2$a=g2. Then we have

$sqrt{n} approx h(n) = g + frac{n – g^2}{2 g} = frac{g + n/g}{2} = frac{g+b}{2}. tag{6}$n​≈h(n)=g+2gn−g2​=2g+n/g​=2g+b​.(6)

And this is exactly what we calculated above.

Geometric interpretation

In general, the second second-order Taylor expansion approximates a possibly
nonlinear function $f(x)$f(x) with a linear function at the point $a$a:

$f(x) approx overbrace{f(a) + f^{prime}(a)(x-a)}^{text{$y$-intercept $+$ slope $times$ $x$-shift}}. tag{7}$f(x)≈f(a)+f′(a)(x−a)​y-intercept + slope × x-shift​.(7)

Thus, the Taylor approximation represents the tangent line to $f(x)$f(x) at the point $(a, f(a))$(a,f(a)). We can see this for $f(x) = sqrt{x}$f(x)=x​ in Figure $1$1. This is a useful visualization because it highlights something
interesting: we expect Heron’s approximation to be worse for
smaller numbers. That’s because the square root function is “more curved”
(speaking loosely) for numbers closer to zero (Figure $2$2, left). As the square root function
flattens out for larger numbers, the linear approximation improves (Figure $2$2,
right).

How good is the approximation?

How good is this method? Did we just
get lucky with $n=33$n=33 or does Heron’s method typically produce sensible
estimates of $sqrt{n}$n​?

To answer this question, I’m replicating a nice figure from an article from MathemAfrica, in
which the author makes a plot with the input number $n$n on the $x$x-axis and the absolute error

$left| sqrt{n} – h(n) right| tag{8}$∣∣∣​n​−h(n)∣∣∣​(8)

on the $y$y-axis (Figure $2$2, blue line). (Note that when programming Heron’s
method, we must decide if we want to find $g^2$g2 by searching numbers greater or
less than $n$n; here, I’ve set $g$g as the first integer less than
the square root of $n$n, or as g = floor(sqrt(n)).) I like this figure because it captures
two interesting properties of Heron’s method. First, as we discussed above, the
Taylor approximation will typically be worse when $n$n is small (when $f(x) = sqrt{x}$f(x)=x​;
this is not true in general). And second, the error drops to zero on perfect
squares and increases roughly linearly between perfect squares.

The MathemAfrica post focuses on lowering this absolute error
by judiciuosly picking the initial guess $g$g. This is interesting as analysis. However, in my mind, this is
unnecessarily complicated for most practical mental math scenarios, i.e. for quick sanity checking rather than in a demonstration or competition. Why it is overly complicated? Well, the relative error,

$frac{left|sqrt{n} – h(n) right|}{sqrt{n}}, tag{9}$n​∣n​−h(n)∣​,(9)

rapidly decays to less than a percentage point or so (Figure $2$2, red line).

If
you’re not using a calculator to compute a square root, you’re probably just
getting a rough idea of a problem. And if we actually wanted to lower the absolute error and didn’t care about a human’s
mental limits, we should just expand the Taylor approximation to higher orders.