Homework Help: Newton's Method Variation

1. Oct 9, 2011

Scootertaj

1. The problem statement, all variables and given/known data
The most commonly used algorithm for computing $\sqrt{a}$ 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/$\sqrt{a}$ (it then only remains to multiply by a to get $\sqrt{a}$.

2. Relevant equations
xn+1 = 1/2 (xn + a/xn)
xn+1 = xn - f(xn)/f'(xn)

3. 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/$\sqrt{a}$ ?
Moreover, how do they get to the equation?

2. Oct 9, 2011

Dick

Skip finding the single reciprocal. Just use Newton's method to solve f(x)=a-1/x^2. The solution to that is x=1/sqrt(a), yes?

3. Oct 9, 2011

Scootertaj

Update: I figured out I believe.... This is what I did:

xn+1 = xn - f(xn) / f'(xn) = xn - (1/xn2 - A)(-xn3/2) = xn - xn(-1/2 + Axn2) = xn(1+1/2-Axn2) = xn/2 * (3-Axn2).

Last edited: Oct 9, 2011
4. Oct 9, 2011

Scootertaj

Ahh, that would make it easier, I'll go with that! (afterall, it gives the same solution).