Fastest method implementing number sqare root in string (1000000 digits)

Question

What is fastest algorithm implementing a square root of decimal contained in strings. This decimal can have 1000000 digits.

Anyone can tell me something about it?

Answer 1

Newton's method should work fine for you: Square Root for Bigint in F# .

Newton's method requires big decimal division. A somewhat simpler method which requires only squaring is just binary search on the square root.

Answer 2

Use 'lsqrt' (Just google for some code) and adjust it for your number type. I used the same approach to deal with big numbers in IronScheme.

Seems to work well.

Edit:

This returns an 'integer' root and a remainder.