20041205, 04:12  #1 
Aug 2003
Snicker, AL
7×137 Posts 
Fastest possible algorithm to calculate the square root of a 10,000,000 digit number
I've played around with 3 different methods of calculating the square root of very large numbers. I would describe each of them as excruciatingly slow. Does anyone know of an algorithm that can produce the sqrt in less than several hours? Alternatively, is there a way to improve existing algorithms?
Fusion 
20041205, 04:18  #2 
Dec 2003
Hopefully Near M48
2·3·293 Posts 
I would think a very effective algorithm would be just Newton's Method. To get a starting guess, just divide the exponent of the original number by 2.

20041205, 05:22  #3 
Aug 2003
Snicker, AL
7·137 Posts 
Thanks Jinydu, but the question is specific to a number that does NOT already have an exponent. More specifically, if I have a number that is 10,000,000 digits long, is there an algorithm to calculate the sqrt in minimum time. Newton's method works very well for small numbers but it becomes cumbersome with anything much over 50 digits and by 10,000,000 digits, its crawling.
Another item to add is that I don't need extreme precision. I need the sqrt such that ((sqrt(X))^2) < X < ((sqrt(X)+1)^2) and using whole numbers only. Fusion 
20041205, 05:53  #4 
6809 > 6502
"""""""""""""""""""
Aug 2003
101Γ103 Posts
2·47·101 Posts 
To get your 'exponent' count the digits (this is trivial to do with a program).

20041205, 06:15  #5 
Aug 2002
320_{10} Posts 
What are you using to manipulate such large numbers? With numbers that big any algorithm is going to bit a big sluggish.
Newton's algorithm has quadratic convergence so should be reasonibly quick. You can always cut the iterations short if you don't want such precision. There's even better methods which converge faster. X_0 = 1 X_(n+1) = (X_n + A/X_n)*(1/2) Limit n>Inf, X_n = Sqrt(A) The multiplication could be done quickly by a bit shift. 
20041205, 06:36  #6  
"Richard B. Woods"
Aug 2002
Wisconsin USA
7692_{10} Posts 
Quote:


20041205, 08:01  #7  
Aug 2002
2^{6}·5 Posts 
Quote:
(Hmm, I guess my unfortunate ordering of statements could be construed as that.) Last fiddled with by ColdFury on 20041205 at 08:02 

20041205, 11:02  #8  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2998_{16} Posts 
Quote:
It's fast. Unfortunately, it uses rather a lot of storage. A rather more serious answer: I'd use Newton's method. I'd precalculate 1/N so that division can be performed with the fast multiplication method you will need anyway. To get the initial approximation to sqrt(N), count the digits (in the base of your representation of course) , evaluate a floating point square root of the most significant digit(s) and then use that extended by half the number of digits in N. This approach will give you a dozen or two correct bits for the initial approximation. As Newtonian iteration has quadratic convergence (in this case anyway) the number of correct bits will double each time. If your number has 2^26 bits or so and your initial approximation has 2^5 bits correct, you then need another 21 (or 22) iterations to get the accurate integer square root. There are ways of speeding it up. For instance, you don't need fullprecision arithmetic for the early iterations. Increase the precision as you go. You may find superquadratic converging algorithms faster . All these approaches require more time, space and research than I'm prepared to perform right now. They are left as an exercise, as I've already given you something to be getting on with. Paul 

20041206, 06:44  #9  
Aug 2002
500_{8} Posts 
Quote:


20041206, 08:38  #10  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2998_{16} Posts 
Quote:
Sorry for the confusion. I think everything else is OK, especially the advice about working with limited precision in the early iterations and, of course, doubling that precision at each step. Paul 

20041206, 13:23  #11  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
Last fiddled with by cheesehead on 20041206 at 13:27 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Square Root Days  davar55  Lounge  0  20160316 20:19 
Finding the square root of a large mersenne number  Fusion_power  Math  29  20101014 17:05 
Square root of 3  Damian  Math  3  20100101 01:56 
"ODD" Square root Algorithm  petrw1  Math  3  20080315 07:35 
fastest general number primalityproving algorithm?  ixfd64  Math  3  20031217 17:06 