This page demonstrates two methods for computing the arithmetic square root of a positive number x. The first method is simpler algorithmically, but has a lower convergency rate. Both methods are iterative, consist of repeating similar steps, and intended for using on computers or calculators.
The implementations allow the user to choose the value of x, the desired accuracy, and the initial guess. In both cases the initial guess can be chosen to be equal x. The initial guess is essential for the convergency speed.
The square root is approximated by the midpoint of the interval between a lower bound (which is 0) and an upper bound, initially chosen above the square root value. Each iteration consists of computing the middle point of the current interval and switching either to the left or to the right subinterval depending on the square of the midpoint. After each iteration the length of the interval containing the square root decreases in a factor of 2. The iterations are continued until the length of the interval gets below the desired accuracy level.
lower_bd = 0
upper_bd = x
do {
midpoint = (lower_bd + upper_bd)/2
if (midpoint2 < x) then lower_bd = midpoint
else upper_bd = midpoint
guess = midpoint
}
while ( upper_bd - lower_bd > accuracy )
|
Repeat the following process until you are as close to the square root as you wish to be:
guess_new = x;
do {
guess_old = guess_new
guess_new = (guess_old + x/guess_old)/2
}
while ( |guess_old - guess_new|/guess_new > accuracy )
|