Methode zur Berechung des Kehrwertes \begin{eqnarray}\frac{1}{z}\end{eqnarray} einer Zahl z ∈ ℚ mit \begin{eqnarray}\frac{1}{2}\le z\lt 1\end{eqnarray}.

Sie beruht auf der Überlegung, daß \begin{eqnarray}\frac{1}{z}=\frac{1}{1-x}\cdot \frac{1+{x}_{0}}{1+{x}_{0}}\cdot \frac{1+{x}_{1}}{1+{x}_{1}}\cdot \cdots \cdot \frac{1+{x}_{k}}{1+{x}_{k}}\end{eqnarray} für x = 1 − z gilt, und mit der Wahl x_j = x^2j für j = 0, …, k, auch die Gleichung \begin{eqnarray}(1-x)\cdot (1+{x}_{0})\cdot (1+{x}_{1})\cdot \ldots \cdot (1+{x}_{k})=1-{x}_{k+1}\end{eqnarray} erfüllt ist. Hieraus folgt für k \begin{eqnarray}{P}_{k}(x)=\displaystyle \prod _{i=0}^{k}(1+{x}_{i}),\end{eqnarray} daß \begin{eqnarray}\mathop{\mathrm{lim}}\limits_{k\to +\infty }{P}_{k}(x)=\frac{1}{z}\end{eqnarray} gilt. Soll der Kehrwert bis zu einer Genauigkeit von 2⁻ⁿ berechnet werden, so kann für die Zwischenrechnungen eine binäre Zahlendarstellung mit \begin{eqnarray}n+4+\lceil \mathrm{log}(\lceil \mathrm{log}(n+2)\rceil -1)\rceil \end{eqnarray}

Stellen benutzt werden. Das Verfahren wird nach \begin{eqnarray}k=\lceil \mathrm{log}(n+2)\rceil -1\end{eqnarray}

Iterationen abgebrochen.

[1] Omondi, R.: Computer Arithmetic Systems: Algorithms, Architecture, and Implementations. Prentice Hall New York London, 1994.
[2] Wegener, I.: Effiziente Algorithmen für grundlegende Funktionen. B.G. Teubner Verlag Stuttgart, 1989.