Integer square root

In mathematics and 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,

${\mbox{isqrt}}(n)=\lfloor {\sqrt {n}}\rfloor .$

Algorithm

To calculate ${\sqrt {n}}$, and in particular, isqrt(n), one can use Newton's method for the equation $x^{2}-n=0,$ which gives us the recursive formula

${x}_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {n}{x}}_{k}\right),\ k\geq 0.$

One can choose for example $x_{0}=n$ as initial guess.

The sequence $\{x_{k}\}$ converges quadratically to ${\sqrt {n}}$ as $k\to \infty .$ It can be proved (the proof is not trivial) that one can stop as soon as

$|x_{k+1}-x_{k}|$ < 1

to ensure that $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor .$

Domain of computation

Let us note that even if ${\sqrt {n}}$ is irrational for most n, the sequence $\{x_{k}\}$ 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.

Stopping criterium

One can prove that $c=1$ is the largest possible number for which the stopping criterium

$|x_{k+1}-x_{k}|$ < c

ensures $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor$ in the algorithm above.

Since actual computer calculations involve roundoff errors, one needs to use c < 1 in the stopping criterium, e.g.,

$|x_{k+1}-x_{k}|$ < 0.5.

See also

• Wikisource: integer square root