Methods and apparatus for binary division using look-up table
View Patent ↗Improved methods of operating a digital data processor to perform binary division include estimating reciprocals of at least selected divisors based on value accessed from a look-up table. For divisors in a first numerical range, the estimation can be based on a value stored in a first look-up table at an index defined by the divisor. For divisors in a second numerical range, the estimation can be based on an index that is a bitwise-shifted function of the divisor. The methods can be applied to scalar and vector binary division.
1. In a method of operating a digital data processor to perform binary division, the improvement comprising
estimating a reciprocal of a divisor that has a value within a first range of values as a function of a value stored in a first look-up table at an index that is a function of the divisor, the first look-up table comprising estimates for each of respective integer divisors in the first range,
and that has a value within a second first range of values as a function of a value stored in a second look-up table at an index that is a function of a bitwise-shifted value of the divisor, the second look-up table comprising estimates for each of respective groups of plural integer divisors in the second range.
2. In the method of claim 1 , the further improvement comprising comparing the divisor with a threshold value to determine whether to estimate the reciprocal as a function of a value stored in the first table or the second table.
3. In the method of claim 1 , the further improvement wherein
at least one of the respective groups has 2 x divisors, and
the estimating step includes retrieving, for an integer divisor that has a value within the second range, a reciprocal estimate stored in the second look-up table at an index that is a function of a value of the divisor bitwise-shifted by x bits.
4. A method of operating a digital data processor to estimate a quotient of a binary integer dividend by a binary integer divisor, the method comprising the steps of:
A. responding to a divisor that is in a first numeric range of values by accessing a reciprocal estimate from a first look-up table, where such accessing includes using the divisor as an index to the first look-up table, the first look-up table comprising estimates for each of respective integer divisors in the first range,
B. responding to a divisor that is in a second numeric range of values by accessing a reciprocal estimate from a second look-up table, where such accessing includes using a bitwise-shifted value of the divisor as an index to the second look-up table, the second look-up table comprising estimates for each of respective groups of plural integer divisors in the second range,
C. generating a first quotient estimate as a function of the
(i) dividend, and
(ii) the reciprocal estimate accessed in steps (A) or (B).
5. In the method of claim 4 , the further improvement wherein at least one of the respective groups has 2 x divisors.
6. A method of operating a digital data processor to estimate a quotient of a binary integer dividend by a binary integer divisor, the method comprising the steps of:
A. responding to a divisor that is in a first numeric range of values by accessing a reciprocal estimate from a first look-up table, where such accessing includes using the divisor as an index to the first look-up table,
B. responding to a divisor that is in a second numeric range of values by accessing a reciprocal estimate from a second look-up table, where such accessing includes using a bitwise-shifted value of the divisor as an index to the second look-up table,
C. generating a first quotient estimate as a function of the
(i) dividend, and
(ii) the reciprocal estimate accessed in steps (A) or (B)
D. generating a further quotient estimate as a function of an error in the first quotient estimate.
7. A method of operating a digital data processor to estimate a quotient of a binary integer dividend by a binary integer divisor, the method comprising the steps of:
A. responding to a divisor that is in a first numeric range of values by accessing a reciprocal estimate from a first look-up table, where such accessing includes using the divisor as an index to the first look-up table,
B. responding to a divisor that is in a second numeric range of values by accessing a reciprocal estimate from a second look-up table, where such accessing includes using a bitwise-shifted value of the divisor as an index to the second look-up table,
C. generating a first quotient estimate as a function of the
(i) dividend, and
(ii) the reciprocal estimate accessed in steps (A) or (B)
D. generating a further quotient estimate as a function of an error in the first quotient estimate
wherein the step of generating the further quotient estimate includes incrementing the first quotient estimate.
8. A method of operating a digital data processor to estimate a quotient of a binary integer dividend by a binary integer divisor, the method comprising the steps of:
A. responding to a divisor that is in a first numeric range of values by accessing a reciprocal estimate from a first look-up table, where such accessing includes using the divisor as an index to the first look-up table,
B. responding to a divisor that is in a second numeric range of values by accessing a reciprocal estimate from a second look-up table, where such accessing includes using a bitwise-shifted value of the divisor as an index to the second look-up table,
C. generating a first quotient estimate as a function of the
(i) dividend, and
(ii) the reciprocal estimate accessed in steps (A) or (B)
D. generating a further quotient estimate as a function of an error in the first quotient estimate
wherein the step of generating the further quotient estimate includes twice incrementing the first quotient estimate.
9. A method of operating a vector processor to estimate a plurality of quotients of a plurality of binary integer dividends divided by a plurality of binary integer divisors, the method comprising the steps of:
A. loading a dividend vector with the plurality of binary integer dividends,
B. loading a divisor vector with the plurality of binary integer divisors;
C. generating a reciprocal estimate vector register by
i) concurrently comparing each of at least a selected plurality of divisors in the divisor vector to a threshold,
ii) accessing a first look-up table to concurrently determine reciprocal estimates for at least divisors in the divisor vector having a first range of values with respect to the threshold,
where such accessing includes using each respective divisor as an index to the first look-up table, the first look-up table comprising estimates for each of respective integer divisors in the first range,
iii) accessing a second look-up table to concurrently determine reciprocal estimates for at least divisors in the divisor vector having a second range of values with respect to the threshold, where such accessing includes using a bitwise-shifted value of each respective divisor as an index to the second look-up table, the second look-up table comprising estimates for each of respective groups of plural integer divisors in the second range,
D. generating concurrently a plurality of first quotient estimates, the generating step including multiplying each of the reciprocal estimates determined in step (C) by a corresponding one of the dividends.
10. In the method of claim 9 , the further improvement wherein at least one of the respective groups has 2 x divisors.