Finding the value of for is equivalent to seeking a positive number whose square yields : . In other words, the solution to .
We can find by solving . It is by mere inspection. can also be obtained by solving , again, by mere inspection. But ‘mere inspection’ can only go so far. For Example, what is ?
Method for finding the square root of a positive real number date back to the acient Greek and Babylonian eras. Heron’s algorithm, also known as the Babylonian method, is an algorithm named after the – century Greek mathematician Hero of Alexandria, It proceeds as follows:
- Begin with an arbitrary positive starting value .
- Let be the average of and
- Repeat step 2 until the desired accuracy is achieved.
This post offers an analysis of Heron’s algorithm. Our aim is a better understanding of the algorithm through mathematics.
Let us begin by arbitrarily choosing a number . If , then is , and we have guessed the exact value of the square root. Otherwise, we are in one of the following cases:
Both cases indicate that lies somewhere between and .
Let us define as the relative error of approximating by :
The closer is to , the better is as an approximation of .
Let be the mid-point of and :
and, the relative error of approximating ,
i.e., lies between and .
We can generate more values in stages by
Consequently, we can prove that
Assume when ,
Since (11) implies
(10) and (13) together implies
It follows that
(15) indicates that the error is cut at least in half at each stage after the first.
Therefore, we will reach a stage that
It can be shown that
Assume when k = p,
From (17) and (18), we see that eventually, the error decreases at an exponential rate.
Illustrated below is a script that implements the Heron’s Algorithm:
/* a - the positive number whose square root we are seeking x0 - the initial guess eps - the desired accuracy */ square_root(a, x0, eps) := block( [xk], numer:true, xk:x0, loop, if abs(xk^2-a) < eps then return(xk), xk:(xk+a/xk)/2, go(loop) )$
Suppose we want to find and start with . Fig. 2 shows the Heron’s algorithm in action.