Title: Use Heron's method to estimate square roots in Python

[Estimates of square roots] I recently saw a post showing a clever trick for estimating square roots. That sort of thing is clickbait for math majors, so I had to take a closer look. I'll get back to database examples in a day or two.

Heron's Method

The method is based on Heron's method, which you can read about in the Wikipedia article Square root algorithms. It was named after Heron of Alexandria (aka Hero of Alexandria) who described it in his work Metrica in 60 CE.

To find the square root of S, start with some guess x₀ and then iterate the following function until you get the accuracy that you want.

[Heron's method for calculating square roots]

The Trick

That's great and works well, but the trick I saw used a single calculation. To get from Heron's method to the trick, start by rearranging the earlier equation like this:

[Rearranging Heron's method]

Now let R be the perfect square that's closest to S. For example, if S is 97 (so we're trying to find the square root of 97), then R is 100. Let r be the square root of R (10 in this example).

If you plug r into the equation in place of x_n you get this:

[The trick for estimating square roots]

So the trick is basically to make an initial guess (the closest perfect square) and then perform one iteration of Heron's method.

Python Tests

Obviously there's no need to use this trick in Python because you can just calculate math.sqrt(S) or S ** 0.5. This example just verifies that the trick works.

The following estimate_root function uses the trick to estimate the square root of a number.

def estimate_root(s): '''Estimate s's square root.''' # Find the nearest number that is a perfect square. root = math.sqrt(s) root1 = math.floor(root) root2 = root1 + 1 square1 = root1 * root1 square2 = root2 * root2 if abs(square1 - s) < abs(square2 - s): root = root1 square = square1 else: root = root2 square = square2 # Calculate the estimate. return (s + square) / (2 * root)

The code first calculates the number's square root and then finds the closest integers larger and smaller than the square root. It squares those integer roots and sees which squared value is closer to the target number s.

The code then applies the trick and returns the result.

The program uses the following code to test the method.

print() print('Num Estimate Root Diff Percent') print('--- -------- ---- ---- -------') num_i = 10 for i in range(1, num_i + 1): estimate = estimate_root(i) root = math.sqrt(i) diff = estimate - root pct = diff / root print(f'{i:3} {estimate:10.6f} {root:10.6f} {diff:10.6f} {pct:.6%}')

This code loops through a bunch of values and prints the estimate, square root, difference, and percentage difference. The following text shows the results.

Num Estimate Root Diff Percent --- -------- ---- ---- ------- 1 1.000000 1.000000 0.000000 0.000000% 2 1.500000 1.414214 0.085786 6.066017% 3 1.750000 1.732051 0.017949 1.036297% 4 2.000000 2.000000 0.000000 0.000000% 5 2.250000 2.236068 0.013932 0.623059% 6 2.500000 2.449490 0.050510 2.062073% 7 2.666667 2.645751 0.020915 0.790526% 8 2.833333 2.828427 0.004906 0.173461% 9 3.000000 3.000000 0.000000 0.000000% 10 3.166667 3.162278 0.004389 0.138793%

Not only are the estimates very close to the correct value, but the percentage errors are extremely small.

Conclusion

This trick lets you calculate approximate square roots relatively easily. It's probably not easily enough to do it in your head, but it's an interesting use of Heron's method.

In my next post, I'll graph the results so we can more easily see just how good a job this method does. (Then I'll get back to database examples.)

Download the example to experiment with it and to see additional details.