In number theory, the integer square root (isqrt) of a positive integer n is the positive integer m which is the greatest integer less than or equal to the square root of n,
Contents
- Algorithm
- Using only integer division
- Using bitwise operations
- Domain of computation
- Stopping criterion
- References
For example,
Algorithm
One way of calculating
The sequence
to ensure that
Using only integer division
For computing
By using the fact that
one can show that this will reach
However,
Using bitwise operations
With *
being multiplication, <<
being left shift, and >>
being logical right shift, a recursive algorithm to find the integer square root of any natural number is:
Or, iteratively instead of recursively:
function integerSqrt(n): if n < 0: error "integerSqrt works for only nonnegative inputs" # Find greatest shift. shift = 2 nShifted = n >> shift # We check for nShifted being n, since some implementations of logical right shifting shift modulo the word size. while nShifted ≠ 0 and nShifted ≠ n: shift = shift + 2 nShifted = n >> shift shift = shift - 2 # Find digits of result. result = 0 while shift ≥ 0: result = result << 1 candidateResult = result + 1 if candidateResult*candidateResult ≤ n >> shift: result = candidateResult shift = shift - 2 return resultDomain of computation
Although
Stopping criterion
One can prove that
ensures
In implementations which use number formats that cannot represent all rational numbers exactly (for example, floating point), a stopping constant less than one should be used to protect against roundoff errors.