Integer square root

From Wikipedia, the free encyclopedia

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.

Contents

[edit] Algorithm

To calculate \sqrt{n}, and in particular, isqrt(n), one can use Newton's method for the equation x2 − n = 0, which gives us 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.

One can choose for example x0 = n as initial guess.

The sequence {xk} 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

| xk + 1 − xk | < 1

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

[edit] Domain of computation

Although \sqrt{n} is irrational for most n, the sequence {xk} 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.

[edit] Stopping criterion

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

| xk + 1 − xk | < 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.

| xk + 1 − xk | < 0.5.

[edit] See also

[edit] External links

v • d • e
Number-theoretic algorithms
Primality tests
Sieving algorithms
Integer factorization algorithms
Other algorithms
Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.
Languages