# Methods and complexity for computing square roots

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

Yiorgos

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.

Thanks for taking the time to reply.

Do you know how much Newton's method cost?

Hi,

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

Last edited by a moderator:
Hi,

http://numbers.computation.free.fr/Constants/Algorithms/inverse.html" [Broken]
So, to compute $$\sqrt{A}$$ with Newton's method, we will use the iterations:

$$x_{n+1} =\frac{3}{2}x_n-\frac{1}{2}A{x_n}^3$$

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:
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 $$\sqrt{2}$$ to n-digits precision.

See if that helps.