Divider with quotient digit prediction

Claim 2

In a data processing machine for performing division in a base B greater than two of a divided 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 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 i for the generation of a quotient digit Q i ; means, responsive to one or more leading digit of the divisor and one or more leading digit of the partial remainder PR i , for predicting a quotient digit for Q i , the predicted quotient digit being a least possible quotient digit; means, connected to the means for predicting and the first means for generating and responsive to the predicted quotient digit for Q i , for selecting a first multiple of the set consisting of multiples of the divisor that is closed to without exceeding the predicted quotient digit times the divisor; first means for subtracting the selected first multiple of the divisor from the partial remainder PR i to update the partial remainder PR i ; means for determining whether the updated partial remainder PR 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 i is not less than the divisor, including means for subtracting one times the divisor from the updated partial reminder PR i to further update the partial remainder PR i , means for incrementing the predicted quotient digit for Q i , and means for returning the updated partial remainder PR 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 i is less than the divisor, for storing the predicted quotient digit as Q i .

Claim 3

The apparatus of claim 1, wherein the means for generating a set consisting of multiples of the divisor includes: a plurality of multiple storing means for storing respective multiples of the divisor.

Claim 4

The apparatus of claim 1, wherein the means for predicting a quotient digit for Q i includes: an addressable table storing means for storing a table of possible quotient digits addressed in response to the one or more leading digit of the divisor and the one or more leading digit of the partial remainder PR i .

Claim 5

The apparatus of claim 1, wherein the means for predicting a quotient digit for Q i includes: means for receiving the one leading digit LDD of the divisor and the two leading digits LPR of the partial remainder PR i ; and means for generating the predicted quotient digit according to the following equation: Q.sub.i =the integer (LPR/(LDD+1)).

Claim 6

The apparatus of claim 4, wherein the means for predicting a quotient digit for Q i includes addressable table storing means for storing a table of possible quotient digits addressed by the one leading divisor digit and the two leading partial remainder digits.

Claim 7

The apparatus of claim 1, wherein the base is 10.

Claim 8

The apparatus of claim 1 wherein the means for storing the predicted quotient digit as Q i further includes: means, responsive to the storing of the final quotient digit Q Y for storing the updated partial remainder PR Y that is determined to be less than the divisor as a remainder of the division.

Claim 9

The apparatus of claim 1, further including means responsive to the prediction of a quotient digit for Q i for predicting an error code for the predicted quotient digit for Q i .

Claim 10

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 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 i for the generation of a quotient digit Q i ; means, responsive to one or more leading digit of the divisor and one or more leading digit of the partial remainder PR i , for predicting a quotient digit for Q i ; means, connected to the means for predicting and the first means for generating and responsive to the predicted quotient digit for Q 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 i to update the partial remainder Pr i ; second means for subtracting the selected second multiple of the divisor from the partial remainder PR i to further update the partial remainder PR i , if a second multiple is selected; means for determining whether the updated partial remainder PR 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 i is not less than the divisor, including means for subtracting one times the divisor from the updated partial remainder PR i , to further update the partial remainder PR i , means for incrementing the predicted quotient digit for Q i , and means for returning the updated partial remainder PR 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 i is less than the divisor, for storing the predicted quotient digit as Q i .

Claim 11

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 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 i for the generation of a quotient digit Q i ; means, responsive to one or more leading digit of the divisor and one or more leading digit of the partial remainder PR i , for predicting a quotient digit for Q i ; means, connected to the means for predicting and the first means for generating and responsive to the predicted quotient digit for Q 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 i to update the partial remainder Pr i ; second means for subtracting the selected second multiple of the divisor from the partial remainder PR i to further update the partial remainder PR i , if a second multiple is selected; means for determining whether the updated partial remainder PR 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 i is not less than the divisor, including means for subtracting one times the divisor from the updated partial remainder PR i , to further update the partial remainder PR i , means for incrementing the predicted quotient digit for Q i , and means for returning the updated partial remainder PR 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 i is less than the divisor, for storing the predicted quotient digit as Q i .

Claim 12

The apparatus of claim 9, wherein the means for generating a set consisting of multiples of the divisor includes: a plurality of multiple storing means for storing respective multiples of the divisor.

Claim 13

The apparatus of claim 10, wherein the base is 10, and the respective multiples include one times the divisor, two times the divisor, three times the divisor and six times the divisor.

Claim 14

The apparatus of claim 9, wherein the means for predicting a quotient digit for Q i includes: an addressable table storing means for storing a table of possible quotient digits addressed in response to the one or more leading digit of the divisor and the one or more leading digit of the partial remainder PR i .

Claim 15

The apparatus of claim 9, wherein the means for predicting a quotient digit for Q i includes: means for receiving the one leading digit LDD of the divisor and the two leading digits LPR of the partial remainder PR i ; and means for generating the predicted quotient digit according to the following equation: Q.sub.i =the integer (LPR/(LDD+1)).

Claim 16

The apparatus of claim 9, wherein the means for predicting a quotient digit for Q i includes addressable table storing means for storing a table of possible quotient digits addressed by the one leading divisor digit and the two leading partial remainder digits.

Claim 17

The apparatus of claim 9, wherein the base is 10.

Claim 18

The apparatus of claim 9 wherein the means for storing the predicted quotient digit as Q i further includes: means, responsive to the storing of the final quotient digit Q Y for storing the updated partial remainder PR Y that is determined to be less than the divisor as a remainder of the division.

Claim 19

The apparatus of claim 9, further including means responsive to the prediction of a quotient digit for Q i for predicting an error code for the predicted quotient digit for Q i .

Claim 22

The method of claim 18, wherein the step of predicting a quotient digit for Q i includes the step of: storing a table of possible quotient digits addressed in response to the one or more leading digit of the divisor and the one or more leading digit of the partial remainder PR i .

Claim 23

The method of claim 18, wherein the step of predicting a quotient digit for Q i includes the step of: receiving the one leading digit LDD of the divisor and the two leading digits LPR of the partial remainder PR i ; and generating the predicted quotient digit according to the following equation: Q.sub.i =the integer (LPR/(LDD+1)).

Claim 24

The method of claim 18, wherein the step of predicting a quotient digit for Q i includes the step of: storing a table of possible quotient digits addressed by the one leading divisor digit and the two leading partial remainder digits.

Claim 25

The method of claim 18, wherein the base is 10.

Claim 26

The method of claim 18 further including after the storing of the final quotient digit Q Y the step of: storing the updated partial remainder PR Y that is determined to be less than the divisor as a remainder of the division.

Claim 27

The method of claim 18, further including after the step of selecting a first multiple of the divisor, the steps of: selecting a second multiple of the set consisting multiples of the divisor if the predicted quotient digit times the divisor is greater than the first multiple; and subtracting the selected second multiple of the divisor from the partial remainder PR i to further update the partial remainder PR i , if a second multiple is selected.

Claim 28

The method of claim 24, wherein the base is 10 and the set consisting of multiples includes one times the divisor, two times the divisor, three times the divisor and six times the divisor.