I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?
$\begingroup$
$\endgroup$
16
-
5$\begingroup$ 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}$. $\endgroup$– Joe SilvermanCommented Jul 8, 2013 at 19:02
-
$\begingroup$ 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. $\endgroup$– François G. DoraisCommented Jul 8, 2013 at 19:40
-
1$\begingroup$ @FrançoisG.Dorais, you have gone mad with power. $\endgroup$– Will JagyCommented Jul 8, 2013 at 20:20
-
1$\begingroup$ @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$? $\endgroup$– KavehCommented Jul 8, 2013 at 20:40
-
3$\begingroup$ 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$. $\endgroup$– KavehCommented Jul 8, 2013 at 20:53
|
Show 11 more comments
3 Answers
$\begingroup$
$\endgroup$
3
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.
answered Jul 8, 2013 at 20:05
-
1$\begingroup$ 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. $\endgroup$ Commented Jul 9, 2013 at 12:19
-
$\begingroup$ I asked the orginal question and find satisfactory answers in the citations by F. G. Dorais. $\endgroup$ Commented Jul 9, 2013 at 19:14
-
1$\begingroup$ @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. $\endgroup$ Commented Jul 9, 2013 at 20:53
$\begingroup$
$\endgroup$
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$.
answered Jul 8, 2013 at 23:38
$\begingroup$
$\endgroup$
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.
answered Jul 8, 2013 at 20:29