Methods and complexity for computing square roots

[geor]

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!

Yiorgos

 

[qntty]

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)?

I don't know if it's the most commonly used, but Newton's method is used a lot.

 

[mathman]

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.

 

[geor]

Thanks for taking the time to reply.

Do you know how much Newton's method cost?

 

[BobMonahon]

Hi,
Here's link that myght help:

http://numbers.computation.free.fr/Constants/Algorithms/inverse.html"

 

[geor]

Hi,
Here's link that might help:

http://numbers.computation.free.fr/Constants/Algorithms/inverse.html"

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...

 

[BobMonahon]

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.