What's the efficient algorithm to find the Integer square root of a very large number, digit by digit?
algorithm, c, integer-arithmetic, square-root
Solution
You can implement long division method to compute square root which is being taught at school. You can implement this method for base 10 and the result is computed digit by digit from left to right. You can stop once integer part is calculated.
Problem
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.