Integer square root
From Wikipedia, the free encyclopedia
In number theory (a branch of mathematics), 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,
For example, isqrt(27) = 5 because 
and 
.
Contents |
[edit] Algorithm
To calculate 
, and in particular, isqrt(n), one can use Newton's method for the equation x2 − n = 0, which gives us the recursive formula
One can choose for example x0 = n as initial guess.
The sequence {xk} converges quadratically to as 
. It can be proved (the proof is not trivial) that one can stop as soon as
- | xk + 1 − xk | < 1
to ensure that 
[edit] Domain of computation
Let us note that even if is irrational for most n, the sequence {xk} contains only rational terms. Thus, with Newton's method one never needs to exit the field of rational numbers in order to calculate isqrt(n), a fact which has some theoretical advantages in number theory.
[edit] Stopping criterion
One can prove that c = 1 is the largest possible number for which the stopping criterion
- | xk + 1 − xk | < c
ensures 
in the algorithm above.
Since actual computer calculations involve roundoff errors, one needs to use c < 1 in the stopping criterion, e.g.,
- | xk + 1 − xk | < 0.5.
