Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have to take the square root of a number so large that there is no way to compute it directly. I thought if I divided it up into smaller pieces, I might be able to get this done in as few steps as possible. I found the digit-by-digit square root algoritm on Wikipedia, and thought it might be useful. The page stated that it works for any base, but it didn't give a general way to apply it to an arbitrary base-$n$.

How do I implement it in base-$65536$, for example? And does this allow me to speed it up by taking the square root of the individual pairs of base-$65536$ digits using some sqrt function already available to me?

My focus is mainly on the math behind the algorithm. Is the algorithm suitable to a base-$2^{16}$ context, or do I gain no advantage over binary, for example?

share|cite|improve this question
The algorithm based on single bits is surprisingly fast since it avoids divisions and multiplications of digit-sized integers and replaces them by bit-shifting. This may be a reason that you do not find the other variants explained in detail. The digit based algorithm is about as fast (or here slow) as Newton's method. -- The generalized root computation is explained in – LutzL May 30 '14 at 20:47
If you just want the square root you should probably use something like newtons method. – Kristoffer Ryhl May 30 '14 at 20:48
@Darksonn I'm afraid that for extremely large numbers, Newton's method may take longer to converge. This algorithm also represents each digit exactly. – Brian J. Fink May 30 '14 at 20:53
@BrianJ.Fink If you pick a proper approximation newtons method should have quadratic convergence, regardless how large the number is. Also, what kind large is this number? Maybe post the number on pastebin. – Kristoffer Ryhl May 30 '14 at 21:05
@Darksonn I not only need to check one extremely large number, I need to check a whole lot of them! The truth is I have no idea what numbers I'll have to check, just that they'll eventually get really huge! – Brian J. Fink May 30 '14 at 21:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.