Herons Method to Find Square Root of a Number

Sunday, Oct 20, 2019
Python Algorithms

Heron's method is a simple algorithm to find the square root of any number. It starts by guessing the square root to be mean of 1 and the number itself. This guess becomes an upper limit of the approximation while the number divided by the guess becomes the lower limit. These two limits are compared and if they match within desired number of decimal places, we stop and the guess is reported as the answer.

Problem: Find the square root of a number.

Input: A positive number N and number of decimal places P for how close the answer should be.

Output: Square root of the number.

Algorithm Flowchart


Implementation in Python

def squareroot(n, p):
    """function to compute squareroot using heron's algorithm
    n is the number to calculate the squareroot of,
    p is decimal points of precision"""
    xg = (1 + n)/2
    for i in range(1000):
        xl = n / xg
        xu = xg
        if round(xl, p) == round(xu, p):
        xg = (xl + xu) / 2
    return(round(xl, p))

Is it correct?

To check correctness, I will compare it with built-in math.sqrt() function. Note that the default relative tolerance of isclose() is 1e-09, so I set the precision of squareroot() to 10:

from math import sqrt
from math import isclose
nums = [2, 23, 165, 1867, 16498]
for n in nums:
    print(isclose(sqrt(n), squareroot(n, 10)))
In [56]: for n in nums:                                    
    ...:     print(isclose(sqrt(n), squareroot(n, 10)))    
In [57]:

Ok, the algorithm works correctly with our few test cases. I am curious now to find how fast (or slow!) it is compared to the built-in function.