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

Question

Hello,

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: http://stackoverflow.com/questions/608514/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.

Answer 3

BigSquareRoot