# Algorithm to Compute Square Root

by Gilmar

The almost universally used algorithm to compute √a is the recursion

Xn+1 = ½ (xn + a/xn)

Easily obtained by means of Newton’s method.

Assume you are working with very simple processor that only supports addition, subtraction multiplication and having ( a subtraction of one the exponent of base-2 number), but not a general divide. Devise a fast algorithm for this processor to directly approximate 1/√a (it then only remains to multiply with a to get √a).

Other approaches than Newton's method are available for generating fast iterative method's for putting √a =x(1-r)- ½ where r= 1- (/ x²)/a

Is an identity for any (positive) value of x. Hence the iteration

xn+1= xn(1-r)-1/2 where r=1 x²n/a

Will converge in one step to √a. However, this iteration is useless since it requires the computation of a square root (we could have just as well computed√a. Directly!).

To make this iteration useful, we note that r becomes small if xn is a good approximation to √a which suggests replacing (1-r) - 1/2 by truncated Taylor expansion. By including different numbers of terms in the Taylor’s expansion, we get iterative methods of arbitrary order of convergence.

From the preceding discussion , derive the quadratically convergent recursion

xn+1 =( x²n/2)(3- x²n/2)

Explain why it is quadratically convergent.

C. Suppose a=4, determine in which intervals around the root x=2 the two interactions (1) and(2) will

Converge to the root x-2, and

Diverge to α

Hint: Plot separate graphs of y=1/2(x+4/x) and y= x²n/2(3- x²n/4), respectively.