Fastest possible algorithm to calculate the square root of a 10,000,000 digit number

[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

[jinydu]

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.

[Fusion_power]

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

[Uncwilly]

To get your 'exponent' count the digits (this is trivial to do with a program).

[ColdFury]

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.

[cheesehead]

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.)

[ColdFury]

(... 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.)

[xilman]

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

[ColdFury]

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)

[xilman]

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

[cheesehead]

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.