Square Root (Newton's Algorithm) Using Recursion

Question

Can someone explain to me this recursive pseudocode that finds the square root of a number? I find it difficult to understand since I'm not given what n, p, and e inputs stand for. Thanks.

if abs(e^2 - n) < p
    SR(n,p,e) = e     
else
    SR(n,p,e) = SR(n,p,(e+n/e)/2)

(e begins at n)

Answer 1

n is the number you want the square root of, e is an estimate for the square root, and p is the precision you want, i.e. the error you are willing to tolerate. The algorithm says: if e is "close enough" to the answer, i.e. e^2 is within p of n, then e is the answer you are looking for; otherwise, try a better estimate, (e+n/e)2. Why is that a better estimate? if e is larger than sqrt(n), then n/e will be smaller than sqrt(n), so sqrt(n) will be between e and n/e, so try the average of e and n/e as your next estimate. (And vice versa if e is less than sqrt(n)).

Hope this helps,

Bruce

Answer 2

There's rather more to Newton's algorithm than just going from one estimate to a "better estimate". There's some detailed maths behind why the better estimate is what it is.

The idea is that to find the solution to ANY equation of the form f(x) = 0, (apart from a few exceptional cases), if you have an approximation to x, you can get a BETTER approximation, by looking at the rate of change of f(x), which is often written f'(x), and using that to work out how much you have to adjust your estimate by, to get a much better estimate of the true solution.

In the case of a square root, that is, we want to find x=sqrt(n), we can write f(x)=x^2-n and f'(x)=2x, then use Newton's algorithm to find the right x to make f(x)=0. What this means is that if we have an estimate e, then to work out our next estimate, we look at f(e)=e^2-n, and we ask how much we have to change e to get rid of this error. Since the rate of change of f is f'(x), which is 2e at the point (e,e^2-n), we should divide e^2-n by 2e to work out how much we have to adjust e by, to get our next estimate.

That is, our next estimate should be

  e - (e^2-n) / 2e
= e - (e / 2)  + (n / 2e)
= (e + n / e) / 2

More information on Newton's algorithm can be found at http://tutorial.math.lamar.edu/Classes/CalcI/NewtonsMethod.aspx (which has a lovely diagram that explains how it works) and at http://www.math.brown.edu/UTRA/linapprox.html which goes into some of the more technical detail.