Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Methods and complexity for computing square roots

  1. Jan 18, 2009 #1
    Hello everybody,

    Let's say we want to compute sqrt(x), where x is an integer
    of n digits. Then what is the cost of the computation, in
    terms of big O notation and n?

    And a second question: what is the algorithm for finding the
    square root that is most commonly used in computers and
    calculators (just a name or a link will do)?

    Thanks a lot in advance!

  2. jcsd
  3. Jan 18, 2009 #2
    I don't know if it's the most commonly used, but newton's method is used a lot.
  4. Jan 18, 2009 #3


    User Avatar
    Science Advisor

    There is an algorithm which resembles long division (I learned it in 4th grade) for taking square roots. It should take about the same time as long division.
  5. Jan 18, 2009 #4
    Thanks for taking the time to reply.

    Do you know how much Newton's method cost?
  6. Jan 18, 2009 #5
    Here's link that myght help:

    http://numbers.computation.free.fr/Constants/Algorithms/inverse.html" [Broken]
    Last edited by a moderator: May 3, 2017
  7. Jan 18, 2009 #6
    Thanks, that is helpful, indeed..
    So, to compute [tex]\sqrt{A}[/tex] with Newton's method, we will use the iterations:

    [tex]x_{n+1} =\frac{3}{2}x_n-\frac{1}{2}A{x_n}^3[/tex]

    Can you help me compute the complexity of this one?
    Let's say that A has n digits and let's also say it is a square
    of an integer...
    Last edited by a moderator: May 3, 2017
  8. Jan 19, 2009 #7
    The complexity of the calculation depends on the number of digits you want in the result, I think. This might be a simpler way to get started: Calculate [tex]\sqrt{2}[/tex] to n-digits precision.

    See if that helps.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook