How to Use Newton's Method for Computing 1/\sqrt{a} for a Simple Processor

[Scootertaj]

Homework Statement

The most commonly used algorithm for computing $\sqrt{a}$ is the recursion x_n+1 = 1/2 (x_n + a/x_n), 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}$.

Homework Equations

x_n+1 = 1/2 (x_n + a/x_n)
x_n+1 = x_n - f(x_n)/f'(x_n)

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:
x_n+1 = (x_n) (3 - A (x_n)^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?

 

[Dick]

Homework Statement

The most commonly used algorithm for computing $\sqrt{a}$ is the recursion x_n+1 = 1/2 (x_n + a/x_n), 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}$.

Homework Equations

x_n+1 = 1/2 (x_n + a/x_n)
x_n+1 = x_n - f(x_n)/f'(x_n)

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:
x_n+1 = (x_n) (3 - A (x_n)^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?

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?

 

[Scootertaj]

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

x_n+1 = x_n - f(x_n) / f'(x_n) = x_n - (1/x_n² - A)(-x_n³/2) = x_n - x_n(-1/2 + Ax_n²) = x_n(1+1/2-Ax_n²) = x_n/2 * (3-Ax_n²).

 

[Scootertaj]

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?

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