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, isqrt(27) = 5 because $5\cdot 5=25 \le 27$ and $6\cdot 6=36 > 27$.

Algorithm

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

${x}_{k+1} = \frac{1}{2}\left(x_k + \frac{ n }{x_k}\right), \quad k \ge 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₀ = 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₀ is rational. Thus, with this method it is unnecessary to exit the field of rational numbers in order to calculate 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.

Since actual computer calculations involve roundoff errors, a stopping constant less than 1 should be used, e.g.

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

See also

• Methods of computing square roots

External links

• A geometric view of the square root algorithm