3
$\begingroup$

Is Newton's method when it comes to, say, a 4000 bit number a serious consideration for computing the floor square root function?

$\endgroup$
  • $\begingroup$ It'd help if you could explain the method you found... $\endgroup$ – fgp Dec 9 '13 at 14:30
  • $\begingroup$ 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. $\endgroup$ – fgp Dec 9 '13 at 14:32
  • $\begingroup$ 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. $\endgroup$ – fgp Dec 9 '13 at 15:02
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. I'd probably accept this as the correct answer after looking at the references mentioned. $\endgroup$ – user114628 Dec 9 '13 at 14:45
  • $\begingroup$ Thank you again. The references you provided completely answers my question. It saved me a lot of unnecessary extra work :) $\endgroup$ – user114628 Dec 9 '13 at 15:04
  • $\begingroup$ By the way, there is a typo in the abstract of the paper. The given complexity is for an input of size $2 n$. $\endgroup$ – user114628 Dec 24 '13 at 13:07
  • $\begingroup$ Is it faster than Gary Tarolli's implementation of Newtons Method ? $\endgroup$ – Romantic Electron Jul 30 '17 at 9:44
  • $\begingroup$ @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. $\endgroup$ – gammatester Jul 30 '17 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy