Digit-by-digit calculation of square root

[jd12345]

Years back i learned the digit-by-digit calcualtion of square root like this : http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation

But i don't know why this works. Wikipedia gives kind of an explanation but i don't understand it. How does this method work?

 

[mfb]

Let's call the initial number a. The part already determined form the square root is p.

The basic idea is like that: For each step, find the next digit such that the squared value (consisting of p plus the new digit) is smaller than a, but the same number with one more as next digit would (squared) give a value larger than a.
Now, how do we find this digit?

We already know that p^2<a and the difference d=a-p^2 can be calculated.
Now we add a small value x/10 to p. This gives (p+x/10)^2=p^2+2px/10+x^2/100 and should be a better approximation to the square root.

Therefore, we want to find an x with 2px/10+x^2/100 <= d.
To avoid decimal digits, shift everything by two places, which is equivalent to a multiplication of 100 on both sides:
20 p x + x^2 <= 100d.
100d is now called c.
x (20p+x) <= c
Which is the formula used by the wikipedia page to find the next digit. Does that help?

 

[coolul007]

There is an explanation in George Crystal's(sp) Algebra(2 volumes), mine is in a box somewhere, but if you can find a copy it's in there.