Methods and complexity for computing square roots

  • Thread starter geor
  • Start date
  • #1
35
0
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
 

Answers and Replies

  • #2
290
2
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.
 
  • #3
mathman
Science Advisor
7,871
450
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
35
0
Thanks for taking the time to reply.

Do you know how much Newton's method cost?
 
  • #5
12
0
Hi,
Here's link that myght help:

http://numbers.computation.free.fr/Constants/Algorithms/inverse.html" [Broken]
 
Last edited by a moderator:
  • #6
35
0
Hi,
Here's link that might help:

http://numbers.computation.free.fr/Constants/Algorithms/inverse.html" [Broken]
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:
  • #7
12
0
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.
 

Related Threads on Methods and complexity for computing square roots

  • Last Post
Replies
5
Views
30K
  • Last Post
Replies
5
Views
961
Replies
45
Views
2K
Replies
4
Views
3K
  • Last Post
Replies
14
Views
3K
Replies
14
Views
22K
Replies
9
Views
2K
Replies
3
Views
3K
Replies
17
Views
2K
  • Last Post
Replies
7
Views
3K
Top