mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-12-05, 04:12   #1
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

7×137 Posts
Default 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
Fusion_power is offline   Reply With Quote
Old 2004-12-05, 04:18   #2
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default

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.
jinydu is offline   Reply With Quote
Old 2004-12-05, 05:22   #3
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

7·137 Posts
Default

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
Fusion_power is offline   Reply With Quote
Old 2004-12-05, 05:53   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101Γ—103 Posts

72·197 Posts
Default

To get your 'exponent' count the digits (this is trivial to do with a program).
Uncwilly is online now   Reply With Quote
Old 2004-12-05, 06:15   #5
ColdFury
 
ColdFury's Avatar
 
Aug 2002

5008 Posts
Default

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.
ColdFury is offline   Reply With Quote
Old 2004-12-05, 06:36   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

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.)
cheesehead is offline   Reply With Quote
Old 2004-12-05, 08:01   #7
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26·5 Posts
Default

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
ColdFury is offline   Reply With Quote
Old 2004-12-05, 11:02   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×7×383 Posts
Default

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
xilman is offline   Reply With Quote
Old 2004-12-06, 06:44   #9
ColdFury
 
ColdFury's Avatar
 
Aug 2002

32010 Posts
Default

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)
ColdFury is offline   Reply With Quote
Old 2004-12-06, 08:38   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×7×383 Posts
Default

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
xilman is offline   Reply With Quote
Old 2004-12-06, 13:23   #11
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

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
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Square Root Days davar55 Lounge 0 2016-03-16 20:19
Finding the square root of a large mersenne number Fusion_power Math 29 2010-10-14 17:05
Square root of 3 Damian Math 3 2010-01-01 01:56
"ODD" Square root Algorithm petrw1 Math 3 2008-03-15 07:35
fastest general number primality-proving algorithm? 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.