Integer square root

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 \le 27 and 6\cdot 6=36 > 27.

Algorithm[edit]

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 \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_{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[edit]

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[edit]

One can prove that c=0.5 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 half should be used to protect against roundoff errors.

See also[edit]

External links[edit]