Algorithm to Compute Square Root
The almost universally used algorithm to compute √a is the recursion
= ½ (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
(1-r)-1/2 where r=1 x²n
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
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