Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms? Thanks.

share|improve this question

migrated from mathoverflow.net Jul 8 '13 at 19:39

This question came from our site for professional mathematicians.

2  
Not sure this really qualifies as a research level question, you might be better off posting on MathStackexchage. But a very fast and easy algorithm to compute square root of $A$ to $N$ decimal places for some reasonable $N$ is Newton's algorithm to find a root of $X^2 - A$. So pick an initial $x_0$, say $x_0=A/2$, and then iteratively compute $x_{i+1} = \dfrac{x_i}{2}-\dfrac{A}{2x_i}$. –  Joe Silverman Jul 8 '13 at 19:02
    
The documentation and source code to GMP could be used as a reference. Also, do note that the size of the integer is important; different methods are better for differently sized integers. Any other special properties the integer might have (such as being a perfect square, or near a power of 2) are also very relevant. –  Hurkyl Jul 8 '13 at 19:42
2  
Do you want the integer square root? That is, the integer $i$ such that $i^2 \le n \lt (i+1)^2$? Or do you want an approximate rational number $r$ with $r^2\approx n$? And do you want an algorithm that is suitable for pencil-and-paper, for an electronic digital computer, or for something else? –  MJD Jul 8 '13 at 19:42

3 Answers 3

Method 1

Newton's Method converges quadratically. $a \ge 0, x_0 \ne \sqrt{a}$

$$x_{k+1} = \dfrac{1}{2}\left(x_{k} +\dfrac{a}{x_{k}}\right)$$

Method 2

$n \ge 0, x_n \gt \sqrt{a}$ for all $n \gt 0$.

$$x^2_{k+1}-a = \left[\dfrac{x^2_{k} - a}{2x_n}\right]^2$$

Method 3

Third order method, $n \ge 0$

$$x_{n+1} = \dfrac{x_n(x_n^2 + 3a)}{2x^2_n+a}$$

Method 4

See Math World Bhaskara-Brouncker algorithm

Additional Methods (also see references)

Wiki Methods of computing square roots

share|improve this answer
    
Your method 1 is missing a factor of $1/2$, I think. –  Daryl Jul 8 '13 at 22:13
1  
@Daryl: Thank you for catching that, I accidentally deleted it before posting when I was cleaning up! Thanks! Regards –  Amzoti Jul 8 '13 at 22:38
    
Nice details & overview (& links, to boot!) (+) –  amWhy Jul 9 '13 at 0:06
    
@amWhy: Thank you. Surprising how many interesting algorithms there are for that! ;-) –  Amzoti Jul 9 '13 at 1:19

The Newton's Method will not work if you are limited to integer arithmetic, which this problem seems to presuppose.

You know for sure that $s = \sqrt{N} \in [N/2, N]$.

Start with $x = N/2$ (integer division by 2) and check:

  • if $x^2 = N$, you are done;
  • if $x^2 < N$, you know that $s \in [x,N]$;
  • if $x^2>N$ then you know $s \in [N/2,x]$.

Set $s$ to be the midpoint of the resulting interval and repeat the previous step.

The idea is to split the interval in half each iteration. The running time is worst-case $\log(N)$.

share|improve this answer
2  
If $N \ge 9$, it is not true that $\sqrt N \in [N/2,N]$ –  Ross Millikan Jul 8 '13 at 20:06
    
$\log(N)$ arithmetic operations is not $\log(N)$ time.... –  Hurkyl Jul 8 '13 at 20:52

"efficient" rather depends on what you constraints are. For instance, if you have enough memory to store some floats, but little cpu time, then you can store a look up table for all integers until some power of 10. So say you had to find $\sqrt(1632397825)$. You could write: $$\sqrt{1732397825} =\sqrt{ 17*10^8 + 32397825}\sim \sqrt{17}\cdot 10^4 + \epsilon$$

To calculate $\epsilon$, use the fact that: $$\sqrt{a^2+b}\sim a + \frac{b}{2a} - \frac{b^2}{8a^3} + ...$$ So in our example, $$\sqrt{1732397825} \sim 41622.06575$$ Quite close to the true value of: $$\sqrt{1732397825}=41622.08338$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.