Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. 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?

share|improve this question
4  
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
    
Paul Zimmerman wrote several papers about this. In particular, together with Bertot, Magaud and Zimmerman have formally verified the square root algorithm used in GMP, which is presumably current state of the art. –  François G. Dorais Jul 8 '13 at 19:40
1  
@FrançoisG.Dorais, you have gone mad with power. –  Will Jagy Jul 8 '13 at 20:20
1  
@François, not sure I understand. Numerical analysis algorithms work on a larger set of values but they also work on integers. Is the question finding $\lfloor \sqrt{n} \rfloor$ given $n$? –  Kaveh Jul 8 '13 at 20:40
3  
In any case, it is not very clear what OP is looking for: just some algorithm to roughly compute the square root or an algorithm to compute the square root accurately up to a given precision $p$. –  Kaveh Jul 8 '13 at 20:53
show 11 more comments

3 Answers

There are many algorithms that are suitable for different contexts. Asymptotically, a combination of Newton's method with FFT is the best known method according to R. P. Brent Multiple-precision zero-finding methods and the complexity of elementary function evaluation [Analytic computational complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1975), 151–176; MR0423869]. However, for numbers with up to a million digits, Zimmerman's Karatsuba square root algorithm gives better results. For numbers up to 50 digits or so, a good implementation of the traditional schoolbook method is perhaps even better.

share|improve this answer
1  
Asymptotically, the best known method is a combination of Newton’s method with whatever the fastest known multiplication algorithm is. At the moment, that would be Fürer’s algorithm. –  Emil Jeřábek Jul 9 '13 at 12:19
    
I asked the orginal question and find satisfactory answers in the citations by F. G. Dorais. –  Richard Warren Jul 9 '13 at 19:14
    
@RichardWarren: Thank you! If you want, you can accept my answer by clicking the checkmark next to it. This is to indicate that you found this answer satisfactory for your query. –  François G. Dorais Jul 9 '13 at 20:53
add comment

If you want the square root of an odd perfect square then one approach is to find the square root 2-adically.

Suppose you want the square root of $n$. You can use the usual Newton-Raphson algorithm for the equation $f(x)=x-n/x=0$, working modulo $2^N$, for some large enough $N$. That's the iteration $x \rightarrow -x(-3n+x^2)/(2n)$. However, that requires division by $n$. You can achieve this by first using Newton-Raphson to solve for $g(x) = 1/x-n = 0$ to find $n^{-1}$ modulo $2^N$. That's $x\rightarrow x(2-nx)$. So two Newton-Raphson solves are required.

Requires only addition, subtraction and multiplication modulo $2^N$. Note also that it may converge to $-\sqrt n$.

share|improve this answer
add comment

In case what is desired is the floor of the square root of an integer, there were two surprises when i wrote this in C++ for numbers up to a bound, in my case $2^{31} - 1.$ There is no impediment to doing Newton's method with integers. The first trick is that you can get an infinite loop where Newton's method cycles back and forth between the floor and ceiling of the (real) square root. So I told it to continue Newton until successive values differ by less than 5 in absolute value, then iterate, first a little up, then down until low enough.

The other trick was about the upper bound. You need to tell it that, if the target number is at least as large as the largest square below the bound, in my case $46340^2 = 2147395600,$ then do not bother doing anything, the floor of the square root is known, in my case 46340. If this is not done, you can get an infinite loop for a slightly different reason. And, of course, if the number is from 1 to 3, the floor of the square root is automatically 1.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.