Square root algorithm I would like an efficient algorithm for square root of a positive integer.  Is there a reference that compares various square root algorithms?
 A: 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.
A: 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$.
A: 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. 
