Newton-Raphson Division

The Newton – Raphson division method uses the Newton method to find the reciprocal value of a denominator and to multiply it by a numerator for the result of the quotient . ${\displaystyle N\in \mathbb {N} }$ ${\displaystyle Z\in \mathbb {Z} }$ ${\displaystyle Q:=Z/N}$

Because of its particular importance for computer technology, the procedure is presented below for the dual system . But it can also be used on any other basis.

steps

The steps of the Newton – Raphson division method are:

1. Finding a first approximation for the reciprocal of the denominator . ${\displaystyle X_{0}}$ ${\displaystyle 1/N}$ ${\displaystyle N}$
2. Calculate ever better approximations of the reciprocal. The Newton method is used here. ${\displaystyle X_{1},X_{2},\ldots ,X_{S}}$
3. Calculating the quotient by multiplication of the counter with the reciprocal value of the denominator: . ${\displaystyle Q=ZX_{S}}$

Newton's method

The application of Newton's method requires a function that has a zero at . The obvious function has trivial derivatives that are unsuitable for Newton's method . One useful function is with . Because of this , the graph of the function intersects the axis transversely, i.e. H. non-touching. For which the Newton iteration is ${\displaystyle f(X)}$ ${\displaystyle X=1/N}$ ${\displaystyle f(X)=NX-1}$ ${\displaystyle f(X)=1/X-N}$ ${\displaystyle f'(X)=-1/X^{2}}$ ${\displaystyle f'(X)<0}$ ${\displaystyle X}$

${\displaystyle X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-N \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-NX_{i})=X_{i}(2-NX_{i})}$,

which can be calculated starting from exclusively via multiplication and subtraction (or two fused multiply-add operations). ${\displaystyle X_{i}}$

Convergence speed

If the fault is defined as then: ${\displaystyle \epsilon _{i}=NX_{i}-1}$

${\displaystyle {\begin{aligned}\epsilon _{i+1}&=NX_{i+1}-1\\&=N(X_{i}(2-NX_{i}))-1\\&=2NX_{i}-N^{2}X_{i}^{2}-1\\&=-(N^{2}X_{i}^{2}-2NX_{i}+1)\\&=-(NX_{i}-1)^{2}\\&=-{\epsilon _{i}}^{2}.\\\end{aligned}}}$

This squaring of the error at each step - the so-called quadratic convergence of Newton's method - ensures that the number of correct digits roughly doubles with each iteration ; a property that is particularly valuable when calculating with long numbers .

Since the speed of convergence is exactly quadratic for this method , it follows that

${\displaystyle S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$

Steps are sufficient for a precision of binary digits. That's 3 for single and 4 for both double and extended precision IEEE 754 formats . ${\displaystyle P}$

Finding a first approximation

By bit shifts the denominator can the interval be brought. The counter should experience the same number of shifts so that the quotient remains unchanged. After that one can do a linear approximation of the shape ${\displaystyle N}$ ${\displaystyle 0{,}5\leq N<1}$ ${\displaystyle Z}$

${\displaystyle {\frac {1}{N}}:\approx X_{0}:=T_{1}+T_{2}N}$   with     and   ${\displaystyle T_{1}:={\frac {48}{17}}}$ ${\displaystyle T_{2}:=-{\frac {32}{17}}}$

apply to initiate the procedure.

The coefficients and this linear (polynomial degree 1) approximation result as follows. The relative error is . The minimum value of the maximum error in such an interval is given by the alternant set of Chebyshev applied to the function . The local extremum of takes place when is what the solution has. According to the said alternant set needs this function at the extremum (inside) the opposite sign than at the edges of the interval, have so . For the two unknowns in the two equations, the solution is and , and the maximum relative error is . According to this approximation, the relative error is the initial value ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle |(T_{1}+T_{2}N-1/N)/(1/N)|=|N(T_{1}+T_{2}N)-1|}$ ${\displaystyle [0{,}5\,;\,1[}$ ${\displaystyle F(N)=N(T_{1}+T_{2}N)-1}$ ${\displaystyle F(N)}$ ${\displaystyle F'(N)=0}$ ${\displaystyle N=-T_{1}/(2T_{2})}$ ${\displaystyle F(1/2)=F(1)=-F(-T_{1}/(2T_{2}))}$ ${\displaystyle T_{1}=48/17}$ ${\displaystyle T_{2}=-32/17}$ ${\displaystyle F(1)=1/17}$

${\displaystyle \vert \epsilon _{0}\vert \leq {1 \over 17}\approx 0{,}059.}$

Pseudocode

The following computes the quotient of and to an accuracy of binary digits: ${\displaystyle Z}$ ${\displaystyle N}$ ${\displaystyle P}$

Drücke N aus als M × 2e mit 1 ≤ M < 2 (Standard-Gleitkomma-Darstellung)
N' := N / 2e+1             // Bitverschiebungen resp. Verkleinerung des Exponenten
Z' := Z / 2e+1
X := 48/17 − 32/17 × N'   // erste Näherung mit der gleichen Genauigkeit wie N
repeat  ${\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$ times   // kann für fixes P vorausberechnet werden
    X := X + X × (1 - N' × X)
end
return Z' × X

For a double-precision floating point division, for example, this method requires 10 multiplications, 9 additions and 2 shifts.

literature

• Mário P. Véstias and Horácio C. Neto Decimal Division Using the Newton-Raphson Method and Radix-1000 Arithmetic
• Thomas L. Rodeheffer Software Integer Division

Similar procedures

• Goldschmidt Division
• SRT division