TABLE OF CONTENTS The number of steps in the previously described division methods was linearly proportional to the number of bits, n, while in the division-by-convergence schemes, which will be described in this chapter, the number of steps is proportional to log 2 n. However, the basic operation in the division-by-convergence schemes is not an add/subtract operation but the usually slower multiply operation. Hence, a fast parallel multiplier is necessary to successfully implement these schemes.
Let the divisor D and the dividend N be considered the denominator and numerator, respectively, of the quotient Q. Thus, Q=N/D. This holds if we multiply both numerator and denominator by the same factor R 0, or even by m factors R 0 , R 1 , , R m ?1 . If the factors R i are selected so that the denominator converges to 1, the numerator will converge to Q:
In Equation (8.1) only the quotient is calculated, and a separate computation is necessary if the remainder is needed. Therefore, this division scheme is more suitable for floating-point computations.
The essential step in this method is the selection of the factors to ensure the convergence of the denominator to 1. This selection is based on the following observation: Let the divisor be a normalized binary fraction 0.1 xxxx (where each x is either 0 or 1). Therefore, 1/2 ? D<1 and D=1 ? y,...
