integerSquareRoot

The integer square root of a non-negative integer n, denoted as isqrt(n) or sometimes by a floor symbol, is the largest integer m such that m * m <= n. In other words, it is the floor of the true square root of n. For example, isqrt(10) is 3 because 3 * 3 = 9, which is less than or equal to 10, while 4 * 4 = 16, which is greater than 10. The integer square root is always a non-negative integer.

Calculating the integer square root is a fundamental operation in computer science and number theory. Various algorithms exist for this purpose, with efficiency being a key consideration. Binary search is a common and efficient method. It works by searching for the integer square root within a range, typically from 0 up to n itself (or a tighter upper bound like n/2 + 1 for n > 1). In each step, the algorithm checks the square of the middle element of the current range and adjusts the range accordingly.

Another approach is using Newton's method, adapted for integers. This iterative method converges quickly to the true square root and can be modified to find the integer square root by stopping when the approximation no longer improves. For very large integers, specialized algorithms might be employed to optimize performance. The integer square root has applications in areas such as cryptography, graphics, and number-theoretic algorithms.