# Methods and complexity for computing square roots

• geor
In summary, the conversation discusses the cost of computing the square root of an integer with n digits, in terms of big O notation. It also asks for the most commonly used algorithm for finding square roots in computers and calculators. The expert mentions Newton's method as a commonly used algorithm and provides a link for more information. The conversation also touches upon the complexity of using Newton's method to compute the square root of an integer with n digits.
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

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.

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,
Here's link that myght help:

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

Last edited by a moderator:
BobMonahon said:
Hi,
Here's link that might help:

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

Thanks, that is helpful, indeed..
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.

## 1. What are the different methods for computing square roots?

There are several methods for computing square roots, including the Babylonian method, the Newton's method, and the bisection method. Each method has its own advantages and disadvantages, and may be more suitable for certain situations.

## 2. How do these methods differ in terms of complexity?

The complexity of these methods can vary depending on the number of iterations required to approximate the square root. Generally, the bisection method has the lowest complexity, followed by the Babylonian method, and then the Newton's method. However, the complexity may also be affected by the precision or accuracy required for the computation.

## 3. Which method is the most accurate for computing square roots?

The Newton's method is considered to be the most accurate method for computing square roots, as it can converge to the correct value in fewer iterations compared to other methods. However, its accuracy may be affected by the initial guess and the precision used in the computations.

## 4. Are there any other factors that can affect the complexity of computing square roots?

Yes, the complexity of computing square roots may also be affected by the size of the number being squared, as well as the hardware and software used for the computations. In some cases, the complexity may also depend on the algorithm used to implement the chosen method.

## 5. Can these methods be used for computing square roots of complex numbers?

Yes, these methods can also be applied to compute the square roots of complex numbers. However, the computations may be more complex and may involve additional steps, such as converting the complex number into polar form and applying the chosen method to the magnitude and argument separately.

• General Math
Replies
13
Views
4K
• General Math
Replies
45
Views
4K
• General Math
Replies
13
Views
2K
• General Math
Replies
1
Views
2K
• General Math
Replies
1
Views
3K
• Calculus
Replies
3
Views
4K
• General Math
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
21
Views
997
• General Math
Replies
29
Views
5K
• General Math
Replies
1
Views
1K