 mersenneforum.org > Math Fastest possible algorithm to calculate the square root of a 10,000,000 digit number
 Register FAQ Search Today's Posts Mark Forums Read  2004-12-05, 04:12 #1 Fusion_power   Aug 2003 Snicker, AL 95910 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    2004-12-05, 04:18 #2 jinydu   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.   2004-12-05, 05:22 #3 Fusion_power   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    2004-12-05, 05:53 #4 Uncwilly 6809 > 6502   """"""""""""""""""" Aug 2003 101×103 Posts 5×43×47 Posts To get your 'exponent' count the digits (this is trivial to do with a program).   2004-12-05, 06:15 #5 ColdFury   Aug 2002 26×5 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.   2004-12-05, 06:36   #6

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts Quote:
 Originally Posted by ColdFury X_0 = 1 X_(n+1) = (X_n + A/X_n)*(1/2) Limit n->Inf, X_n = Sqrt(A)
(... which is Newton's method, starting with an initial approximation = 1.)   2004-12-05, 08:01   #7
ColdFury

Aug 2002

26·5 Posts Quote:
 (... which is Newton's method, starting with an initial approximation = 1.)
I wasn't aware I claimed it wasn't.

(Hmm, I guess my unfortunate ordering of statements could be construed as that.)

Last fiddled with by ColdFury on 2004-12-05 at 08:02   2004-12-05, 11:02   #8
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

24×13×53 Posts Quote:
 Originally Posted by Fusion_power 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 Table lookup implemented through binary search.

It's fast. Unfortunately, it uses rather a lot of storage. A rather more serious answer: I'd use Newton's method. I'd pre-calculate 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 full-precision arithmetic for the early iterations. Increase the precision as you go. You may find super-quadratic 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   2004-12-06, 06:44   #9
ColdFury

Aug 2002

26×5 Posts Quote:
 and using whole numbers only.
I just noticed this. Does this mean you have to use integers thru the entire algorithm? I don't know off-hand any square root algorithms that work entirely in the integers. (Unless you're working within a group)   2004-12-06, 08:38   #10
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

24·13·53 Posts Quote:
 Originally Posted by xilman I'd pre-calculate 1/N so that division can be performed with the fast multiplication method you will need anyway.
I don't know what I was thinking of when I wrote that. As Wacky pointed out in personal mail, the reciprocal of N is not needed for the Newton iteration.

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   2004-12-06, 13:23   #11

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts Quote:
 Originally Posted by Fusion_power I need the sqrt such that ((sqrt(X))^2) < X < ((sqrt(X)+1)^2) and using whole numbers only.
I think Fusion needs only floor(sqrt(X)), so use of integer arithmetic throughout the algorithm would be acceptable, though not mandatory.

Last fiddled with by cheesehead on 2004-12-06 at 13:27   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post davar55 Lounge 0 2016-03-16 20:19 Fusion_power Math 29 2010-10-14 17:05 Damian Math 3 2010-01-01 01:56 petrw1 Math 3 2008-03-15 07:35 ixfd64 Math 3 2003-12-17 17:06

All times are UTC. The time now is 17:21.

Tue Nov 30 17:21:51 UTC 2021 up 130 days, 11:50, 0 users, load averages: 1.85, 1.55, 1.52