1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Newton's Method Variation

  1. Oct 9, 2011 #1
    1. The problem statement, all variables and given/known data
    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].

    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/[itex]\sqrt{a}[/itex] ?
    Moreover, how do they get to the equation?
  2. jcsd
  3. Oct 9, 2011 #2


    User Avatar
    Science Advisor
    Homework Helper

    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?
  4. Oct 9, 2011 #3
    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
  5. Oct 9, 2011 #4
    Ahh, that would make it easier, I'll go with that! (afterall, it gives the same solution).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook