Computing square root faster than Newton’s method Is Newton's method when it comes to, say, a 4000 bit number a serious consideration for computing the floor square root function? 
 A: There is Paul Zimmermann's Karatsuba Square Root Algorthm with a complexity of $\frac{4}{3}K(n)$ for n bit inputs ($K(n)$ is the complexity for Karatsuba multiplication). The algorithm is originally published in 
here, and it is described as Algorithm 1.12 SqrtRem in Brent/Zimmermann's
Modern Computer Arithmetic, Cambridge University Press, 2011 (a preliminary version (V0.5.9, Oct. 2010) of the book is available from the authors at http://maths.anu.edu.au/~brent/pd/mca-cup-0.5.9.pdf)
Edit: Regarding the relation to Newton, Zimmermann wrote in the original article:
The current asymptotically fastest known method to compute the squareroot
of a n-word number is using Fast Fourier Transform (FFT) multiplication and Newton's method, with a complexity of $5M(n)$. 
The algorithm presented here is based on Burnikel-Ziegler Karatsuba division.  Given an integer n, our algorithm computes
simultaneously its integer square root $s = \sqrt{n}$ and the corresponding remainder $r = n-s^2.$ It is not asymptotically optimal but very efficient in practice, with a complexity of about $3/2K(n)$ word operations, where $K(n)$ is the number of words operations to multiply two
n-word numbers using Karatsuba's algorithm.
  This low complexity comes both from the beautiful Karatsuba division recently found by Burnikel and Ziegler, and from the careful use of remainders, which avoids unnecessary computations.
