Octave Implementation of Newton-Raphson Division

John Bryan

• Notation
  • N=numerator.
  • D=denominator=M$\times2\,^e$, where M=significand, e=exponent.
  • $D\,^\prime = \frac{D}{2\,^{e+1}}$
  • $N\,^\prime = \frac{N}{2\,^{e+1}}$
  • S=number of Newton iterations.
  • P=bit precision.
  • $X_0 = $ initial approximation to $\dfrac{1}{D\,^\prime}$.
  • $X_i = $ approximation to $\dfrac{1}{D\,^\prime}$ in Newton iteration i.
  • $Q=\text{quotient} = N\,^{\prime}X_S$.



• Equations $$ S = \left\lceil \log_2\frac{P+1}{\log_217}\right\rceil. \tag{eq. 1} $$
  
  $$ \begin{align} X_0 & =\frac{48}{17}-\frac{32}{17}D\,^\prime \\[1.5ex] & = 2.823529411764706 - 1.882352941176471D\,^\prime. \tag{eq. 2} \end{align}$$
  
  $$ \begin{align} X_{i+1} & =X_i-\frac{f(X_i)}{f^\prime(X_i)} \\[1.5ex] & =X_i-\frac{1/X_i-D\,^{\prime}}{-1/X^2_i} \\[1.5 ex] & =X_i+X^2_i(1/X_i-D\,^{\prime}) \\[1.5 ex] & = X_i+X_i(1-D\,^{\prime}X_i). \tag{eq. 3} \end{align} $$
  



• Octave implementation.



• Results.
  
  
  
  • Evaluate 32/27.
    N=32. D=27.
    In floating point representation, $D = 27 = M \times 2\,^e = 1.687500000000000 \times 2\,^4.$ $D\,^\prime = \frac{D}{2\,^{e+1}} = 0.8437500000000000. \qquad N\,^\prime = \frac{N}{2\,^{e+1}} = 1.0000000000000000. $
    $$ S|_{P=53} = \left\lceil \log_2\frac{P+1}{\log_217}\right\rceil \Bigg|_{P=53} = 4. $$ $$ \begin{array}{|c|c|} \hline X_0 & 1.\color{red}{235297187500000} \\\hline X_1 & 1.18\color{red}{3066359405435} \\\hline X_2 & 1.18518\color{red}{1397199049} \\\hline X_3 & 1.1851851851\color{red}{73078} \\\hline X_4 & 1.185185185185185 \\\hline \end{array} $$ $Q = N\,^{\prime}X_4 = (1.000000000000000)(1.185185185185185) = 1.185185185185.$
  
  
  
  • Evaluate -15.27/34.34.
    N=-15.27. D=34.34.
    In floating point representation, $D = 34.34 = M \times 2\,^e = 1.073125000000000 \times 2\,^5.$ $D\,^\prime = \frac{D}{2\,^{e+1}} = 0.53656250000000 \qquad N\,^\prime = \frac{N}{2\,^{e+1}} = -0.2385937500000000. $
    $$ \begin{array}{|c|c|} \hline X_0 & 1.8\color{red}{13531578125000} \\\hline X_1 & 1.86\color{red}{2364475125406} \\\hline X_2 & 1.86371\color{red}{4803561726} \\\hline X_3 & 1.86371578334\color{red}{2525} \\\hline X_4 & 1.863715783343040 \\\hline \end{array} $$ $Q = N\,^{\prime}X_4 = (-0.238593750000000)(1.863715783343040) = -0.444670937682003.$