Dividers:Multiplicative Dividers.

Multiplicative Dividers

Multiplicative methods perform division through iterative multiplications and are employed in systems that have fast multipliers. The Newton method and Goldschmidt’s algorithm are well-known.

The Newton method calculates the reciprocal of the divisor Y by the Newton-Raphson method. Beginning with an approximation to the reciprocal of the divisor, U0, 1/Y is obtained through the iterative calculation of Ui+1 = Ui · (2 – Ui · Y). Multiplying the dividend X with the obtained 1/Y, we can obtain the quotient.

Goldschmidt’s algorithm is based on the fact that the value of a fraction is unchanged by multiplying both the numerator and the denominator by the same number. Namely, X /Y = (X · D0 · D1 · D2 …)/ (Y · D0 · D1 · D2 …) holds. When Di’s are selected so that Y · D0 · D1 · D2 … approaches to 1, X · D0 · D1 · D 2 … approaches X/Y. We can obtain the quotient through the iterative calculations of Di = 2 – Yi , Yi+1 = Yi · Di , and Xi+1 = Xi · Di . We use an approximation to 1/Y as D0.

In either method, an approximation to the reciprocal of the divisor is required. Direct approximation by table look-up or linear interpolation by table look-up followed by multiply-addition can be used. When the precision of the approximation is m-bits, n-bit division can be done through about log2(n/m) iterations. Two multiplications and a complementation are performed in each iteration. The required calculations are almost the same in both methods. The two multiplications in the Goldschmidt’s algorithm are independent of each other, whereas those in the Newton method are performed serially.

Multiplicative division methods are employed in mainframe computers as well as some microprocessors.