Cubic graph

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,

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

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

Algorithm

One way of calculating $\sqrt{n}$ and $\text{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}(x_k+\frac{n}{x_k}),k\ge 0,x_0>0.$

The sequence $\{x_k\}$ converges quadratically to $\sqrt{n}$ as $k\to \mathrm{\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 $\text{isqrt}(n)$, a fact which has some theoretical advantages.

Stopping criterion

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

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

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 should be used to protect against roundoff errors.

See also

• Methods of computing square roots

External links

• A geometric view of the square root algorithm