Divider with quotient digit prediction

In a data processing machine for performing division in a base B greater than two of a dividend having W digits by a divisor having X digits, where W is greater than X, to generate a quotient having Y digits, an apparatus for generating quotient digits Q.sub.i, i=1 to Y, comprising:

• first means for generating a set consisting of N multiples of the divisor, where N is fewer than B-1;
• second means for generating an initial partial remainder PR.sub.i for the generation of a quotient digit Q.sub.i ;
• means, responsive to one or more leading digit of the divisor and one or more leading digit of the partial remainder PR.sub.i, for predicting a quotient digit for Q.sub.i ;
• means, connected to the means for predicting and the first means for generating and responsive to the predicted quotient digit for Q.sub.i, for selecting a first multiple of the set consisting of multiples of the divisor that is closest to without exceeding the predicted quotient digit times the divisor;
• means connected to said means for selecting a first multiple, for selecting a second multiple of the set consisting of multiples of the divisor if the predicted quotient digit times the divisor is greater than the first multiple;
• first means for subtracting the selected first multiple of the divisor from the partial remainder PR.sub.i to update the partial remainder Pr.sub.i ;
• second means for subtracting the selected second multiple of the divisor from the partial remainder PR.sub.i to further update the partial remainder PR.sub.i, if a second multiple is selected;
• means for determining whether the updated partial remainder PR.sub.i is less than the divisor;
• quotient digit incrementing logic, connected to the means for determining and responsive to a determination that the updated partial remainder PR.sub.i is not less than the divisor, including means for subtracting one times the divisor from the updated partial remainder PR.sub.i, to further update the partial remainder PR.sub.i, means for incrementing the predicted quotient digit for Q.sub.i, and means for returning the updated partial remainder PR.sub.i to the means for determining;
• and
• means, connected to the means for determining and responsive to a determination that the updated partial remainder PR.sub.i is less than the divisor, for storing the predicted quotient digit as Q.sub.i.

A method for performing division in a data processing machine in a base B greater than 2 of a dividend having W digits by a divisor having X digits, where W is greater than X, to generate a quotient having Y digits, the data processing machine comprising an array of storage locations and an arithmetic unit with a result storage location operable under control of data process machine programs, comprising the steps for generating the quotient digits Q.sub.i for i=1 to Y, of:

• storing in the array of storage locations, a set consisting of N multiples of the divisor, where N is fewer than B-1;
• generating in the data processing machine an initial partial remainder PR.sub.i for the generation of quotient digit Q.sub.i ;
• predicting in the data processing machine the quotient digit for Q.sub.i in response to one or more leading digit of the divisor and one or more leading digit of the partial remainder PR.sub.i, the predicted quotient digit being a least possible quotient digit;
• selecting in the data processing machine a first multiple of the set consisting of multiples of the divisor that is closest to without exceeding the predicted quotient digit times the divisor;
• subtracting in the arithmetic unit the selected first multiple of the divisor from the partial reminder PR.sub.i to update the partial remainder PR.sub.i ;
• determining in the data processing machine whether the updated partial remainder PR.sub.i is less than the divisor;
• and
• if the updated partial remainder PR.sub.i is not less than the divisor, then under control of the data processor machine subtracting in the arithmetic unit 1 times the divisor form the updated partial remainder PR.sub.i to further update the partial remainder PR.sub.i, incrementing in the arithmetic unit the predicted quotient digit for Q.sub.i, and returning the updated partial remainder PR.sub.i to the step of determining whether the updated partial remainder PR.sub.i is less than the divisor, and if the updated partial remainder is less than the divisor, then under control of the data processing machine storing in the result storage location the predicted quotient digit as Q.sub.i.