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 nand 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 whythis 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