# Integer square root

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,

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

For example, ${\mbox{isqrt}}(27)=5$ because $5\cdot 5=25\leq 27$ and $6\cdot 6=36>27$.

## Algorithm

One way of calculating ${\sqrt {n}}$ and ${\mbox{isqrt}}(n)$ is to use Newton's method to find a solution for the equation $x^{{2}}-n=0$, giving the recursive formula

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

The sequence $\{x_{k}\}$ converges quadratically to ${\sqrt {n}}$ as $k\to \infty$. It can be proven that if $x_{{0}}=n$ is chosen as the initial guess, 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

Although ${\sqrt {n}}$ is irrational for almost all $n$, the sequence $\{x_{k}\}$ contains only rational terms when $x_{0}$ is rational. Thus, with this method it is unnecessary to exit the field of rational numbers in order to calculate ${\mbox{isqrt}}(n)$, a fact which has some theoretical advantages.

## Stopping criterion

One can prove that $c=0.5$ is the largest possible number for which the stopping criterion

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

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

In implementations which use number formats that cannot represent all rational numbers exactly (for example, floating point), a stopping constant less than one half should be used to protect against roundoff errors.