Editing Integer square root (section)

===Using only integer division===
For computing <math>\lfloor \sqrt n \rfloor</math> for very large integers ''n'', one can use the quotient of [[Euclidean division]] for both of the division operations.  This has the advantage of only using integers for each intermediate value, thus making the use of [[floating point]] representations of large numbers unnecessary.  It is equivalent to using the iterative formula
<math display="block">x_{k+1} = \left\lfloor \frac{1}{2}\!\left(x_k + \left\lfloor \frac{n}{x_k} \right\rfloor \right) \right\rfloor, \quad k \ge 0, \quad x_0 > 0, \quad x_0 \in \mathbb{Z}.</math>

By using the fact that
<math display="block">\left\lfloor \frac{1}{2}\!\left(x_k + \left\lfloor \frac{n}{x_k} \right\rfloor \right) \right\rfloor = \left\lfloor \frac{1}{2}\!\left(x_k + \frac{n}{x_k} \right) \right\rfloor,</math>

one can show that this will reach <math>\lfloor \sqrt n \rfloor</math> within a finite number of iterations.

In the original version, one has <math>x_k \ge \sqrt n</math> for <math>k \ge 1</math>, and <math>x_k > x_{k+1}</math> for <math>x_k > \sqrt n</math>. So in the integer version, one has <math>\lfloor x_k \rfloor \ge \lfloor\sqrt n\rfloor</math> and <math>x_k \ge \lfloor x_k \rfloor > x_{k+1} \ge \lfloor x_{k+1}\rfloor</math> until the final solution <math>x_s</math> is reached. For the final solution <math>x_s</math>, one has <math>\lfloor \sqrt n\rfloor\le\lfloor x_s\rfloor \le \sqrt n</math> and <math>\lfloor x_{s+1} \rfloor \ge \lfloor x_s \rfloor</math>, so the stopping criterion is <math>\lfloor x_{k+1} \rfloor \ge \lfloor x_k \rfloor</math>.

However, <math>\lfloor \sqrt n \rfloor</math> is not necessarily a [[Fixed point (mathematics)|fixed point]] of the above iterative formula. Indeed, it can be shown that <math>\lfloor \sqrt n \rfloor</math> is a fixed point if and only if <math>n + 1</math> is not a perfect square. If <math>n + 1</math> is a perfect square, the sequence ends up in a period-two cycle between <math>\lfloor \sqrt n \rfloor</math> and <math>\lfloor \sqrt n \rfloor + 1</math> instead of converging.