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\; floor.$

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

Algorithm

To calculate $sqrt\{n\}$, and in particular, $mbox\{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\}\; ight),\; quad\; k\; ge\; 0,\; quad\; x\_0\; >\; 0.$One can choose for example $x\_\{0\}\; =\; n$ as initial guess.

The sequence $\{\; x\_k\; \}$ converges quadratically to $sqrt\{n\}$ as $k\; o\; infty$. It can be proven (the proof is not trivial) that one can stop as soon as:to ensure that $lfloor\; x\_\{k+1\}\; floor=lfloor\; sqrt\; n\; floor.$

Domain of computation

Although $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 $mbox\{isqrt\}(\; n\; )$, a fact which has some theoretical advantages.

topping criterion

One can prove that $c=1$ is the largest possible number for which the stopping criterion :ensures $lfloor\; x\_\{k+1\}\; floor=lfloor\; sqrt\; n\; floor$in the algorithm above.

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

See also

* Methods of computing square roots

External links

* [http://www.codecodex.com/wiki/index.php?title=Calculate_an_integer_square_root Code to calculate the integer square root]
* [http://mathcentral.uregina.ca/RR/database/RR.09.95/grzesina1.html A geometric view of the square root algorithm]