and PG level projects,mini projects and many more here ...

Newton–Raphson division


Newton–Raphson uses Newton's method to find the reciprocal of D, and multiply that reciprocal by N to find the final quotient Q.

The steps of Newton–Raphson are:

1.   Calculate an estimate for the reciprocal of the divisor (D): X_{0}.

2.   Compute successively more accurate estimates of the reciprocal: (X_{1},\ldots,X_{S})

3.   Compute the quotient by multiplying the dividend by the reciprocal of the divisor: Q = NX_{S}.

In order to apply Newton's method to find the reciprocal of D, it is necessary to find a function f(X) which has a zero at X=1/D. The obvious such function is f(X)=DX-1, but the Newton–Raphson iteration for this is unhelpful since it cannot be computed without already knowing the reciprocal of D. Moreover multiple iterations for refining reciprocal are not possible since higher order derivatives do not exist for f(X). A function which does work is f(X)=1/X-D, for which the Newton–Raphson iteration gives

X_{i+1} = X_i - {f(X_i)\over f'(X_i)} = X_i - {1/X_i - D\over -1/X_i^2} = X_i + X_i(1-DX_i) = X_i(2-DX_i)

which can be calculated from X_i using only multiplication and subtraction, or using two fused multiply–adds.

If the error is defined as \epsilon_i = D X_i - 1 \,, then

X_i = {1 \over D} (1 + \epsilon_i) \,

\epsilon_{i+1} = - {\epsilon_i}^2 \,.

Apply a bit-shift to the divisor D to scale it so that 0.5 ≤ D ≤ 1 . The same bit-shift should be applied to the numerator N so that the quotient does not change. Then one could use a linear approximation in the form

X_0 = T_1 + T_2 D \approx \frac{1}{D} \,

to initialize Newton–Raphson. To minimize the maximum of the absolute value of the error of this approximation on interval [0.5,1] one should use

X_0 = {48 \over 17} - {32 \over 17} D \,.

Using this approximation, the error of the initial value is less than

\vert \epsilon_0 \vert \leq {1 \over 17} \approx 0.059 \,.

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

S = \left \lceil \log_2 \frac{P + 1}{\log_2 17} \right \rceil \,

steps is enough to calculate the value up to P \, binary places.