Newton's Iteration

An algorithm for the Square Root of a number $r$ quadratically as $\lim_{n\to\infty} x_n$,

$$x_{n+1}={1\over 2}\left({x_n+{r\over x_n}}\right),$$

where $x_0=1$. The first few approximants to $\sqrt{n}$ are given by

$$1, {\textstyle{1\over 2}}(1+n), {1+6n+n^2\over 4(n+1)}, {1+28n+70n^2+28n^3+n^4\over 8(1+n)(1+6n+n^2)}, \ldots.$$

For $\sqrt{2}$, this gives the convergents as 1, 3/2, 17/12, 577/408, 665857/470832, ....

See also Square Root