Newton's method

The calculator uses sequences derived from refinements of Newton's method (see Les Algorithmes, Bibliothèque Tangente 37, 2013, or Itération et Récurrence, Bibliothèque Tangente 76, 2021).

The function f used here is defined by f (x) = x² ‒ a.

We solve f (x) = 0 because its solution is precisely $\sqrt{a}\backslash sqrt\{a\}$, the quantity we are interested in. Let's implement the algorithm.

The derivative of f is f ' (x) = 2 x, and we have ${\displaystyle \frac{f(x)}{f^{\mathrm{\prime }}(x)}}={\displaystyle \frac{x^2-a}{2x}}={\displaystyle \frac{x}{2}}-{\displaystyle \frac{a}{2x}}\mathrm{.}\backslash dfrac\{f(x)\}\{f\text{'}(x)\}\; =\; \backslash dfrac\{x^2\; -a\}\{2x\}\; =\; \backslash dfrac\{x\}\{2\}\; -\; \backslash dfrac\{a\}\{2x\}.$

This gives Heron's sequence:

Let's now illustrate the method with a = 163. To initialize the computation, we can start with a, or, since 163 lies between 144 = 12² and 169 = 13², with 12.

After just three iterations of the algorithm, the result is remarkable, since $\sqrt{163}=12,7671453348037\dots \backslash sqrt\{163\}\; =\; 12,7671453348037\; \backslash ldots$

In fact, the number of correct decimal places doubles (at least) with each loop—a phenomenon known as quadratic convergence.

Each iteration requires one addition and one division, together with a division by 2, which is easy to program in binary: just three operations in all.

Schönhage's trick ---------------------

The main drawback of Heron's sequence (see above) is that it involves a division: division is a "troublesome" and "slow" operation, even for an electronic circuit. But the division "a / *u_n" can be replaced by an iteration: once again, we use Newton's method to compute the reciprocal 1/b of a real number b > 0. This time we use the function g defined by $g(x)={\displaystyle \frac{1}{x}}-b,g(x)\; =\; \backslash dfrac\{1\}\{x\}-b,$ which gives the sequence v defined by v_n*₊₁ = *v_n(2 ‒ bv_n*).

Indeed: $g(x)={\displaystyle \frac{1}{x}}-b,g(x)\; =\; \backslash dfrac\{1\}\{x\}-b,$ and $g^{\mathrm{\prime }}(x)={\displaystyle \frac{-1}{x^2}},g\text{'}(x)\; =\; \backslash dfrac\{-1\}\{x^2\},$ hence ${\displaystyle \frac{g(x)}{g^{\mathrm{\prime }}(x)}}={\displaystyle \frac{{\displaystyle \frac{1}{x}}-b}{{\displaystyle \frac{-1}{x^2}}}}=-x^2({\displaystyle \frac{1}{x}}-b)=-x+b{x}^2,\backslash dfrac\{g(x)\}\{g\text{'}(x)\}\; =\; \backslash dfrac\{\; \backslash dfrac\{1\}\{x\}-b\}\{\backslash dfrac\{-1\}\{x^2\}\}\; =\; -x^2\; \backslash left(\; \backslash cfrac\{1\}\{x\}\; -b\backslash right)\; =\; -x\; +bx^2,$

that is, $v_{n+1}=v_n-{\displaystyle \frac{g\left(u_n\right)}{g^{\mathrm{\prime }}\left(u_n\right)}}=v_n+v_n-b{v}_n^2=v_n(2-b{v}_n)\mathrm{.}v\_\{n+1\}\; =\; v\_n-\; \backslash dfrac\{g\backslash left(u\_n\backslash right)\}\{g\text{'}\backslash left(u\_n\; \backslash right)\}\; =\; v\_n\; +v\_n\; -bv\_n^2\; =\; v\_n\; \backslash left(\; 2-bv\_n\; \backslash right).$

We can do even better! The German mathematician Arnold Schönhage (born in 1934) had the idea of coupling the two Newton iterations, a combination that proved more efficient than using the two methods separately. To find an approximation to the square root of a > 0, we start with the sequence u, defined by

To compute ${\displaystyle \frac{1}{2u_n}},\backslash dfrac\{1\}\{2u\_n\},$ we use Newton's method to compute reciprocals.

In this setting, we use two sequences, u and v:

$\{\begin{array}{l}{u}_{n+1}=u_n+(a-u_n^2)v_n,\text{[}0,7mm]v_{n+1}=v_n(2-2u_n{v}_n)=v_n+(1-2u_n{v}_n)v_n,\end{array}\backslash left\; \backslash \{\; \backslash begin\{array\}\{l\}\; u\_\{n+1\}\; =\; u\_n\; +\; \backslash left(\; a-u\_n^2\backslash right)\; v\_n,\; \backslash [0,7mm]\; v\_\{n+1\}\; =\; v\_n\; (2-2u\_nv\_n)\; =\; v\_n\; +(1-2u\_nv\_n)v\_n,\; \backslash end\{array\}\; \backslash right.$ with $v_0={\displaystyle \frac{1}{2u_0}}\mathrm{.}v\_0=\; \backslash dfrac\{1\}\{2u\_0\}.$