mersenneforum.org > Math Fastest possible algorithm to calculate the square root of a 10,000,000 digit number
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2004-12-05, 04:12 #1 Fusion_power     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
 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 72·197 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 5008 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
cheesehead

"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

22×7×383 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

32010 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

22×7×383 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
cheesehead

"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

 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 00:55.

Sun Jun 20 00:55:27 UTC 2021 up 22 days, 22:42, 0 users, load averages: 2.14, 2.94, 2.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.