Method and apparatus for performing prescaled division

A method for dividing a dividend by a divisor to yield a selectively rounded quotient of substantially m bits, the method being performed using a rectangular aspect ratio multiplier having a short size input of substantially k multiplier bits and a full size input of substantially m multiplicand bits and addition circuitry, comprising the steps:

• (a) generating a short reciprocal of substantially k bits corresponding to a short reciprocal of the divisor;
• (b) scaling the divisor to generate a divisor residual (.epsilon.) of substantially m bits, by multiplying, in the multiplier, the divisor by the short reciprocal to generate a first product, and partitioning the first product into a term of value unity and the divisor residual (.epsilon.);
• (c) scaling the dividend to generate a first quotient digit (d.sub.1) of substantially k bits and a first remainder fraction (f.sub.1) of substantially m bits, by multiplying, in the multiplier, the dividend by the short reciprocal to generate a second product, and partitioning the second product into the first quotient digit (d.sub.1) and the remainder fraction (f.sub.1);
• (d) generating successor quotient digit and remainder fraction pairs (d.sub.n+1, f.sub.n+1) by performing multiplication and subtraction operations, in the multiplier and the addition circuitry, with a preceding quotient digit (d.sub.n), a preceding remainder fraction (f.sub.n), and the divisor residual(.epsilon.) to obtain a product-sum f.sub.n -.epsilon.d.sub.n), and partitioning the product-sum into the successor quotient digit (d.sub.n+1) and the successor remainder fraction (f.sub.n+1);
• (e) accumulating the first quotient digit (d.sub.1), and a predetermined number of the successor quotient digits into a full precision quotient;
• (f) from a final successor quotient digit (d.sub.F) and a final successor remainder fraction (f.sub.F), generating a sense control signal corresponding to a sense of a final product-sum (f.sub.F -.epsilon.d.sub.F) associated with the full precision quotient by performing multiplication and subtraction operations, in the multiplier and addition circuitry, to obtain the final product sum, the sense control signal being generated such that the final product-sum having a sense of zero indicates that the full precision quotient is infinitely precise, and the final product-sum having a sense that is positive or negative respectively indicates that the full precision quotient is smaller or larger than the infinitely precise quotient by less than one unit in its last place;
• and
• (g) responsive to the sense control signal, generating the selectively rounded quotient of substantially m bits from the full precision quotient according to a one of a plurality of selectable rounding modes.

A method of dividing a dividend by a divisor to yield a partial quotient of substantially m bits, the method being performed using a rectangular aspect ratio multiplier having a short size input of substantially k multiplier bits and a full size input of substantially m multiplicand bits and addition circuitry, comprising the steps:

• (a) generating a short reciprocal of substantially k bits corresponding to a short reciprocal of the divisor;
• (b) scaling the divisor to generate a divisor residual of substantially m bits, by multiplying in the multiplier, the divisor by the short reciprocal to generate a first product, and partitioning the first product into a term of value unity and the divisor residual;
• (c) scaling the dividend to generate a first quotient digit of substantially k bits corresponding to the short size input of the multiplier, and an associated remainder fraction of substantially m bits corresponding to the full size input of the multiplier, by multiplying in the multiplier the dividend by the short reciprocal to generate a second product having substantially m+k bits, and partitioning the second product into the first quotient digit of substantially k bits and the remainder fraction of substantially m bits;
• (d) in each of a predetermined number of passes through the multiplier and addition circuitry, calculating a successive quotient digit of substantially k bits of the partial quotient, corresponding to the short size input of the multiplier, and an associated remainder fraction of substantially m bits corresponding to the full size input of the multiplier, by generating and partitioning a product sum equal to a result of subtracting from a preceding remainder fraction the product of a respective preceding quotient digit and the divisor residual;
• and
• (e) for each pass through the multiplier, accumulating the corresponding quotient digit to yield a partial quotient;
• (f) said predetermined number of passes being determined by a ratio m to k, corresponding to the ratio of the number of bits of the full size input to the number of bits of the short size input of the multiplier;
• (g) whereby increasing the size of the multiplier as measured by an increase in the number of bits in the short size input of the multiplier is associated with a decrease in the execution time of division as measured by a decrease in the number of passes through the multiplier.

A circuit for performing division of a dividend by a divisor, using a short reciprocal for prescaling the divisor to obtain a divisor residual, and iteratively outputting successive multiple bit portions of a partial quotient having an undefined length, the circuit comprising:

• (a) calculation circuitry, including a multiplier, that prescales the dividend to obtain a first product-sum comprising a quotient digit having more than eight bits and a remainder fraction by multiplying the short reciprocal and the dividend in a single pass through the calculation circuitry, and to output the quotient digit;
• (b) the short reciprocal having a number of bits comparable to the number of bits of the quotient digit;
• (c) calculation circuitry, including the multiplier and the addition circuitry, that iteratively generates at least one subsequent product-sum comprising a subsequent quotient digit having more than eight bits and a subsequent remainder fraction, the at least one subsequent product-sum being generated by the addition circuitry and the multiplier, wherein the at least one subsequent product sum equals a result of subtracting from a preceding remainder fraction the product of a respective preceding quotient digit and the divisor residual, the product sum being computed in a single pass through the calculation circuitry, and for outputting the subsequent quotient digit;
• and
• (d) circuitry for accumulating the first quotient digit and the at least one subsequent quotient digits into the partial quotient wherein the length of the partial quotient increases by more than eight bits on each pass through the calculation circuitry.