Estimating Square Roots in Your Head
source link: https://gregorygundersen.com/blog/2023/02/01/estimating-square-roots/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Estimating Square Roots in Your Head
I explore an ancient algorithm, sometimes called Heron's method, for estimating square roots without a calculator.
Imagine we want to compute the square root of a number n. The basic idea of Heron’s method, named after the mathematician and engineer, Heron of Alexandria, is to find a number g that is close to n and to then average that with the number n/g, which corrects for the fact that g either over- or underestimates 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. We start by finding a number that forms a perfect square that is close to 33. Here, let’s pick g=6, since 62=36. Then we compute a second number, b=n/g. In practice, computing b in your head may require an approximation. Here, we can compute it exactly as 33/6=5.5. Then our final guess is the average of these two numbers or
n≈2g+b,(1)
which in our example is
33=5.74456264654...≈26+5.5=5.75.(2)
That is pretty good. The relative error is less than 0.1%! And furthermore, this is pretty straightforward to do in your head when n isn’t too large.
Why does this work?
Intuitively, Heron’s method works because g is either an over- or underestimate of n. Then n/g is an under- or overestimate, respectively, of n. So the average of g and n/g should be closer to n than either g or 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 g2. Put more specifically, we’re making a linear approximation of the nonlinear square root function at the point g2.
To see this, recall that the general form of a Taylor expansion about a point a is
f(x)=f(a)+k=1∑∞k!f(k)(a)(x−a)k+…,(3)
where the notation f(k) denotes the k-th derivative of f. If we define f(x)=x, then
f′(x)=2x1,(4)
and so the second-order Taylor approximation of x is
x≈a+2ax−a.(5)
Now choose x=n, and let h(x) denote the Taylor expansion around a=g2. Then we have
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) with a linear function at the point a:
f(x)≈h(x)=f(a)+f′(a)(x−a)y-intercept + slope × x-shift.(7)
Thus, the Taylor approximation represents the tangent line to f(x) at the point (a,f(a)). We can see this for f(x)=x in Figure 1. 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 2, left). As the square root function flattens out for larger numbers, the linear approximation improves (Figure 2, right).
How good is the approximation?
How good is this method? Did we just get lucky with n=33 or does Heron’s method typically produce sensible estimates of 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 on the x-axis and the absolute error
∣∣∣n−h(n)∣∣∣(8)
on the y-axis (Figure 2, 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 n is small (when 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. 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∣n−h(n)∣,(9)
rapidly decays to less than a percentage point or so (Figure 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.
Recommend
-
136
Whenever we use helpers like io.Copy and ioutil.ReadAll like when we are reading from an http.Response body or uploading a file, we find that these methods block until the process is complete…
-
23
Contents: Getting to a real world case Collecting branch statistics Analyzing virtual calls and jump tables Subscribe to mymailing list to get more...
-
24
Estimating Uncertainty in Machine Learning Models — Part 3 Check out part 1 ( here )and part 2 (...
-
25
One Rep MaxA calculator for estimating your 1RM in weightlifting sportsOne Rep Max is a simple tool for estimating li...
-
13
Researchers are often interested in comparing statistical network models across groups. For example, Fritz and colleagues compared the relations between re...
-
7
Estimating the Fault Tolerant Cost of Classically Intractable Quantum ComputationsEstimating the Fault Tolerant Cost of Classically Intractable Quantum Computations - YouTube Live cha...
-
7
Estimating How Long Will It Take to Build Your MVPSeptember 3rd 2021 new storyTL;DR2 In an...
-
6
Oftentimes when collecting consumer data, there are times when you’re unable to retrieve all the data. Instead of having a lack of data ruin your results, you’ll want to “guestimate” what the data should be. Outline ...
-
3
Python provides us with a perfectly satisfactory method of calculating square roots, the math.sqr...
-
1
In the
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK