What effective algorithm will find the square root of an integer from a very large number, by digit?

Question

I need to write a program to find the integer square root of a number that is thousands of digits. I cannot use Newton Raphson, because I do not have data types for storing and separating such large numbers. I use a long array in C to store the number. Is there any algorithm for finding the square root, possibly iterating over the numbers?

Edit:

I cannot use an external library such as GMP.

Answer 1

You can implement the long division method to calculate the square root taught at school. You can implement this method for base 10, and the result is calculated by a digit from left to right. You can stop the calculation of the integer part.

Answer 2

If you can enter the target number, then you must have a way to store at least one such large number. For Newton-Raphson you only need to halve and add numbers. Think about how to reduce the number without using division.

ETA: Correction: division can be avoided by doubling and subtracting.

Answer 3

You seem to have a lot of unrealistic restrictions on the implementation of "bignum". Can I offer a binary search? At each iteration, find the value "half way" mid = (hi + lo) / 2 and crop the search space as [hi, mid] or [mid, lo] depending on the square of these values.

Not as fast as NR, etc. But you need to converge with careful processing of the values ​​of the squares of the range ...