# Methods and complexity for computing square roots

1. Jan 18, 2009

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

Yiorgos

2. Jan 18, 2009

### qntty

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

3. Jan 18, 2009

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

4. Jan 18, 2009

### geor

Thanks for taking the time to reply.

Do you know how much Newton's method cost?

5. Jan 18, 2009

### BobMonahon

Hi,

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

Last edited by a moderator: May 3, 2017
6. Jan 18, 2009

### geor

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: May 3, 2017
7. Jan 19, 2009

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

See if that helps.