# 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?

• It'd help if you could explain the method you found...
– fgp
Dec 9, 2013 at 14:30
• Oh, and this is a math forum, not a programming forum, so please don't describe algorithmns as JAVA code, but instead in a more mathematical notation. You can of course use if statements and the like if they are necessary, but e.g. should write arithmetic using the usual operators, instead of Java's rather hard to read BigInt API.
– fgp
Dec 9, 2013 at 14:32
• The usual operator notation works fine for big numbers. Some programming languages only allow those to be used with fixed-length integers, but that's exactly the kind of implementation detail that's not interesting when dealing with the math behind algorithmns like these. That's why I suggested that you replace that JAVA code with something that's closer to how such an algorithmn would look in a math textbook. Plus, and more importantly, your question referenences to your own algorithmn, but never actually shows it. That's just weird.
– fgp
Dec 9, 2013 at 15:02

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.

• Thank you. I'd probably accept this as the correct answer after looking at the references mentioned.
– user114628
Dec 9, 2013 at 14:45
• Thank you again. The references you provided completely answers my question. It saved me a lot of unnecessary extra work :)
– user114628
Dec 9, 2013 at 15:04
• By the way, there is a typo in the abstract of the paper. The given complexity is for an input of size $2 n$.
– user114628
Dec 24, 2013 at 13:07
• Is it faster than Gary Tarolli's implementation of Newtons Method ? Jul 30, 2017 at 9:44
• @romantic-electron: I don't know. From Wiki it seems that Gary Tarolli computes the inverse square root, therefore you have to invert it. Zimmermann's algorithm computes the real root and the remainder. The term Karatsuba comes from the algorithm structure, not from the multiplication algorithm, so for large numbers this might be Toom-Cook or FFT. Jul 30, 2017 at 10:21