Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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 en.wikipedia.org/wiki/Shifting_nth_root_algorithm –  LutzL May 30 at 20:47
    
If you just want the square root you should probably use something like newtons method. –  Kristoffer Ryhl May 30 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 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 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 at 21:17

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.