- #1
Scootertaj
- 97
- 0
Homework Statement
The most commonly used algorithm for computing [itex]\sqrt{a}[/itex] is the recursion xn+1 = 1/2 (xn + a/xn), easily derived by means of Newton's method. Assume that we have available to us a very simple processor which only supports addition, subtraction, multiplication, and halving (a subtraction of one in the exponent), but not a general divide operation. Devise a Newton-based algorithm for this processor to compute 1/[itex]\sqrt{a}[/itex] (it then only remains to multiply by a to get [itex]\sqrt{a}[/itex].
Homework Equations
xn+1 = 1/2 (xn + a/xn)
xn+1 = xn - f(xn)/f'(xn)
The Attempt at a Solution
I found something that says the following:
Essentially try to compute a single reciprocal A = 1/a and
then solve f(x) = 1/x^2 - A = 0 (whose solution is x = sqrt(a))
iteratively using Newton's method:
xn+1 = (xn) (3 - A (xn)^2) / 2
I can see how this gets rid of the division, and we can account for the halving by subtracting one in the exponent, but how does this solve for 1/[itex]\sqrt{a}[/itex] ?
Moreover, how do they get to the equation?