In number theory, the integer square root (isqrt) of a non-negative integer n is the non-negative integer m which is the greatest integer less than or equal to the square root of n, For example, Introductory remark Let and be non-negative integers. Algorithms that compute (the decimal representation of) run forever on each input which is not a perfect square. Algorithms that compute do not run forever. They are nevertheless capable of computing up to any desired accuracy . Choose any and compute . For example (setting ): Compare the results with It appears that the multiplication of the input by gives an accuracy of decimal digits. To compute the (entire) decimal representation of , one can execute an infinite number of times, increasing by a factor at each pass. Assume that in the next program () the procedure is already defined and — for the sake of the argument — that all variables can hold integers of unlimited magnitude. Then will print the entire decimal representation of . // Print sqrt(y), without halting void sqrtForever(unsigned int y) { unsigned int result = isqrt(y); printf("%d.", result); // print result, followed by a decimal point while (true) // repeat forever ... { y = y * 100; // theoretical example: overflow is ignored result = isqrt(y); printf("%d", result % 10); // print last digit of result } } The conclusion is that algorithms which compute isqrt() are computationally equivalent to algorithms which compute sqrt(). Basic algorithms The integer square root of a non-negative integer can be defined as For example, because . Algorithm using linear search The following C-programs are straightforward implementations. Linear search ... ... using addition In the program above (linear search, ascending) one can replace multiplication by addition, using the equivalence . // Integer square root // (linear search, ascending) using addition unsigned int isqrt(unsigned int y) { unsigned int L = 0; unsigned int a = 1; unsigned int d = 3; while (a <= y) { a = a + d; // (a + 1) ^ 2 d = d + 2; L = L + 1; } return L; } Algorithm using binary search Linear search sequentially checks every value until it hits the smallest where . A speed-up is achieved by using binary search instead. The following C-program is an implementation. // Integer square root (using binary search) unsigned int isqrt(unsigned int y) {