What's the efficient algorithm to find the Integer square root of a very large number, digit by digit?

Question

I need to write program to find the integer square root of a number which is thousands of digits long. I can't use Newton Raphson as I don't have data types to store and divide such large numbers. I am using a long array in C to store the number. Is there any algorithm to find the square root by maybe iterating over the digits?

Edit:

I can't use external library like GMP.

Answer 1

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

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