https://gregorygundersen.com/blog/2023/02/01/estimating-square-roots/ * Home * Blog * RSS Estimating Square Roots in Your Head I explore an ancient algorithm, sometimes called Heron's method, for estimating square roots without a calculator. Published 01 February 2023 Imagine we want to compute the square root of a number nnn. The basic idea of Heron's method, named after the mathematician and engineer, Heron of Alexandria, is to find a number ggg that is close to n\sqrt {n}n and to then average that with the number n/gn/gn/g, which corrects for the fact that ggg either over- or underestimates n\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=33n=33n=33. We start by finding a number that forms a perfect square that is close to 333333. Here, let's pick g=6g=6g=6, since 62=366^2 = 3662=36. Then we compute a second number, b=n/gb = n /gb=n/g. In practice, computing bbb in your head may require an approximation. Here, we can compute it exactly as 33/6=5.533 / 6 = 5.533/6=5.5. Then our final guess is the average of these two numbers or n[?]g+b2,(1) \sqrt{n} \approx \frac{g+b}{2}, \tag{1} n [?]2g+b ,(1) which in our example is 33=5.74456264654...[?]6+5.52=5.75.(2) \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\%0.1%! And furthermore, this is pretty straightforward to do in your head when nnn isn't too large. Why does this work? Intuitively, Heron's method works because ggg is either an over- or underestimate of n\sqrt{n}n . Then n/gn/gn/g is an under- or overestimate, respectively, of n\sqrt{n}n . So the average of ggg and n/gn/gn/g should be closer to n\sqrt{n}n than either ggg or n/gn/gn/ 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 g2g^2g2. Put more specifically, we're making a linear approximation of the nonlinear square root function at the point g2g^ 2g2. To see this, recall that the general form of a Taylor expansion about a point aaa is f(x)=f(a)+[?]k=1[?]f(k)(a)(x-a)kk!+...,(3) f(x) = f(a) + \sum_{k=1}^{\ infty} \frac{f^{(k)}(a)(x-a)^k}{k!} + \dots, \tag{3} f(x)=f(a)+k=1[?][?] k!f(k)(a)(x-a)k +...,(3) where the notation f(k)f^{(k)}f(k) denotes the kkk-th derivative of fff. If we define f(x)=xf(x) = \sqrt{x}f(x)=x , then f'(x)=12x,(4) f^{\prime}(x) = \frac{1}{2 \sqrt{x}}, \tag{4} f'(x)=2x 1 ,(4) and so the second-order Taylor approximation of x\sqrt{x}x is x[?]a+x-a2a.(5) \sqrt{x} \approx \sqrt{a} + \frac{x-a}{2 \sqrt{a}}. \ tag{5} x [?]a +2a x-a .(5) Now choose x=nx=nx=n, and let h(x)h(x)h(x) denote the Taylor expansion around a=g2a = g^2a=g2. Then we have n[?]h(n)=g+n-g22g=g+n/g2=g+b2.(6) \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)f(x) with a linear function at the point aaa: f(x)[?]h(x)=f(a)+f'(a)(x-a)[?]y-intercept + slope x x-shift.(7) f(x) \ approx h(x) = \overbrace{f(a) + f^{\prime}(a)(x-a)}^{\text {$y$-intercept $+$ slope $\times$ $x$-shift}}. \tag{7} f(x)[?]h(x)=f(a) +f'(a)(x-a) y-intercept + slope x x-shift .(7) Thus, the Taylor approximation represents the tangent line to f(x)f (x)f(x) at the point (a,f(a))(a, f(a))(a,f(a)). We can see this for f (x)=xf(x) = \sqrt{x}f(x)=x in Figure 111. This is a useful visualization because it highlights something interesting: we expect this 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 222, left). As the square root function flattens out for larger numbers, the linear approximation improves (Figure 222, right). [linear_app] Figure 1. A visualization of Heron's method, or a second-order Taylor approximation of f(x)=xf(x) = \sqrt{x}f(x)=x . We construct a linear approximation h(x)h(x)h(x) (red dashed line) to the nonlinear function f(x)f(x)f(x) (blue line). We then guess h(n)h(n)h(n) (black dot). Our error is the absolute vertical difference between h(n)h(n)h (n) (black dot) and n\sqrt{n}n (blue dot). How good is the approximation? How good is this method? Did we just get lucky with n=33n=33n=33 or does Heron's method typically produce sensible estimates of n\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 nnn on the xxx-axis and the absolute error |n-h(n)|(8) \left| \sqrt{n} - h(n) \right| \tag{8} ||| n -h(n)||| (8) on the yyy-axis (Figure 222, blue line). 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 nnn is small (when f(x)=xf(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. [errors] Figure 2. The absolute (blue) and relative (red) errors between the true value n\sqrt{n}n and the estimate using Heron's approximation h (n)h(n)h(n). The errors are zero when nnn is a perfect square and are smaller on average for small nnn than for large nnn. The MathemAfrica post focuses on lowering this absolute error by judiciuosly picking the initial guess ggg. 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, |n-h(n)|n,(9) \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 222, 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. 1. Benjamin, A., & Shermer, M. (2006). Secrets of mental math: the mathemagician's guide to lightning calculation and amazing math tricks. Crown.