US5046038A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for performing division using a rectangular aspect ratio multiplier
Assignee: VIA Cyrix Inc
•
Filing: 1989-08-02
•
Granted: 1991-09-03
•
Expires: 2009-08-02
Abstract
Abstract A method and apparatus for performing division is described which first comprises approximating the short reciprocal of the divisor. A reciprocal bias adjustment factor is added to the approximation and the correctly biased short reciprocal is multiplied by a predetermined number of the most significant bits of the dividend and the product is truncated to generate a first quotient digit value. The multiplication takes place in a multiplier array having a rectangular aspect ratio with the long side having a number of bits at least as large as the number of bits required for the divisor. The short side of the multiplier array has a number of bits slightly greater by several guard bits than the number of bits required for a single quotient digit value, which is also determined to be the number of bits in the short reciprocal. The quotient digit value is multiplied by the full divisor and the exact product is subtracted from the dividend to yield an exact partial remainder. The described steps are repeated to serially generate quotient digit values with exact partial remainders with the preceding partial remainder taking the place of the dividend. The quotient digit values are accumulated to yield a complete quotient. The complete quotient is decremented and the remainder recalculated if the final partial remainder is negative, yielding the full precision unique quotient and non-negative remainder pair.
Inventors
- 👤 Willard B. Briggs
- 👤 David W. Matula
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 09:38
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/48; G06F7/52; G06F7/535; G06F7/491; G06F7/4915; G06F7/4917; G06F7/537; G06F7/5375; G06F2207/00; G06F2207/535; G06F2207/5351; G06F2207/5355
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
274 words
A circuit for performing exact division of a dividend by a divisor, comprising: a rectangular array multiplier; circuitry associated with said multiplier for obtaining a short reciprocal of said divisor; circuitry associated with said multiplier for facilitating the multiplication of said short reciprocal by said dividend to yield a first product; circuitry associated with said multiplier for truncating said first product to have less bits than said divisor to yield a first quotient digit value; circuitry associated with said multiplier for facilitating the generation of a product of said first quotient digit value and said divisor; circuitry associated with said multiplier for computing the difference between said dividend and said product of said first quotient digit value and said divisor to yield a first partial remainder; circuitry associated with said multiplier for facilitating the multiplication of said short reciprocal by said first partial remainder to yield a subsequent product; circuitry associated with said multiplier for truncating said subsequent product to have less bits than said divisor to yield a subsequent quotient digit value; circuitry associated with said multiplier for facilitating the generation of a product of said subsequent quotient digit value and said divisor; and circuitry associated with said multiplier for computing the difference between said first partial remainder and said product of said subsequent quotient digit value and said divisor to yield a new partial remainder, said first quotient digit value and said subsequent quotient digit value calculated such that said partial remainder and said new partial remainder have magnitudes corresponding to less than one unit in the last place of said first quotient digit value and said subsequent quotient digit value, respectively.
Claim 2
Dependent Claim
274 words
A circuit for performing exact division of a dividend by a divisor, comprising: a rectangular array multiplier; circuitry associated with said multiplier for obtaining a short reciprocal of said divisor; circuitry associated with said multiplier for facilitating the multiplication of said short reciprocal by said dividend to yield a first product; circuitry associated with said multiplier for truncating said first product to have less bits than said divisor to yield a first quotient digit value; circuitry associated with said multiplier for facilitating the generation of a product of said first quotient digit value and said divisor; circuitry associated with said multiplier for computing the difference between said dividend and said product of said first quotient digit value and said divisor to yield a first partial remainder; circuitry associated with said multiplier for facilitating the multiplication of said short reciprocal by said first partial remainder to yield a subsequent product; circuitry associated with said multiplier for truncating said subsequent product to have less bits than said divisor to yield a subsequent quotient digit value; circuitry associated with said multiplier for facilitating the generation of a product of said subsequent quotient digit value and said divisor; and circuitry associated with said multiplier for computing the difference between said first partial remainder and said product of said subsequent quotient digit value and said divisor to yield a new partial remainder, said first quotient digit value and said subsequent quotient digit value calculated such that said partial remainder and said new partial remainder have magnitudes corresponding to less than one unit in the last place of said first quotient digit value and said subsequent quotient digit value, respectively.
Claim 3
Dependent Claim
68 words
The circuit of claim 1 and further comprising: circuitry associated with said multiplier for generating a desired number of quotient digit values by reiterating said computations using a new partial remainder to generate each new quotient digit value, all of said quotient digit values calculated such that subsequent partial remainders have magnitudes corresponding to less than one unit in the last place of a preceding quotient digit value.
Claim 4
Dependent Claim
18 words
The circuit of claim 1 and further comprising: circuitry associated with said multiplier for storing said short reciprocal.
Claim 5
Dependent Claim
104 words
The circuit of claim 1 wherein said circuitry for obtaining a short reciprocal comprises: circuitry for adding a reciprocal bias adjustment factor to an approximate reciprocal of said divisor to yield a sum and truncating said sum to yield said short reciprocal, said reciprocal bias adjustment factor chosen to offset accumulated error in said approximate reciprocal and bias said short reciprocal to produce quotient digit values which, when accumlated to form a partial quotient, are always at most one unit in the last place greater than or exactly equal to an infinitely precise value of the quotient truncated to a predetermined number of bits.
Claim 6
Dependent Claim
87 words
The circuit of claim 4 wherein said quotient digit values give rise to a negative partial remainder when said quotient digit values are greater than said exact value, said negative partial remainder causing a succeeding quotient digit value to be negative, thereby causing a product of said succeeding quotient digit value and the divisor operable to reduce the magnitude of said negative partial remainder and, when combined with a preceding quotient digit value, producing a borrowing from the least significant bit of said preceding quotient digit value.
Claim 7
Dependent Claim
103 words
The circuit of claim 4 wherein said circuitry for obtaining a short reciprocal of said divisor further comprises: circuitry associated with said multiplier for computing a final reciprocal approximation equal to the sum of a prior reciprocal approximation and a reciprocal bias adjustment factor chosen to offset accumulated error in said prior reciprocal approximation and bias said final reciprocal approximation to produce quotient digit values which, when accumulated to form a partial quotient, are always at most one unit in the last place greater than or exactly equal to an infinitely precise value of the quotient truncated to a predetermined number of bits.
Claim 8
Dependent Claim
17 words
The circuit of claim 6 wherein said prior reciprocal approximation is equal to said second reciprocal approximation.
Claim 9
Dependent Claim
66 words
The circuit of claim 6 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2 - (N+k) where N is equal to the number of bits of the radix of the quotient digit values and k is a predetermined number of guard bits, said second term being less than said first term.
Claim 10
Dependent Claim
23 words
The circuit of claim 6 wherein said reciprocal bias adjustment factor is equal to the sum of 2 -19 and 2 -22 .
Claim 11
Dependent Claim
146 words
The circuit of claim 1 wherein said circuitry for obtaining a short reciprocal of said divisor, comprises: look-up table circuitry for storing a plurality of reciprocal seed values; retrieval circuitry coupled to said look-up table circuitry for retrieving a particular reciprocal seed value associated with said divisor; circuitry associated with said multiplier and said retrieval circuitry for computing a first term comprising the difference between two and the product of said divisor and said particular reciprocal seed value and for computing a product of said first term and said particular reciprocal seed value to yield a first reciprocal approximation; and circuitry associated with said multiplier for computing a second term comprising the difference between two and the product of said divisor and said first reciprocal approximation and for computing a product of said second term and said first reciprocal approximation to yield a second reciprocal approximation.
Claim 12
Dependent Claim
36 words
The circuit of claim 1 and further comprising: circuitry associated with said multiplier for decrementing a final quotient digit value generated by one unit in the last place if a final partial remainder generated is negative.
Claim 13
Dependent Claim
35 words
The circuit of claim 11 and further comprising: circuitry associated with said multiplier for correcting said final partial remainder by adding said divisor to said final partial remainder if said final partial remainder is negative.
Claim 14
Dependent Claim
45 words
The circuit of claim 1 wherein said circuitry for obtaining a short reciprocal comprises: look-up for table circuitry for storing a plurality of approximate reciprocal values; retrieval circuitry coupled to said look-up table circuitry for retrieving a particular approximate reciprocal value associated with said divisor.
Claim 15
Dependent Claim
107 words
The circuit of claim 13 wherein said circuitry for obtaining a short reciprocal further comprises: circuitry for adding a reciprocal bias adjustment factor to said particular approximate reciprocal value to yield a sum and truncating said sum to yield said short reciprocal, said reciprocal bias adjustment bias adjustment factor chosen to offset error in said particular approximate reciprocal value and bias said short reciprocal to produce quotient digit values which, when accumulated to form a partial quotient, are always at most one unit in the last place greater than or exactly equal to an infinitely precise value of the quotient truncated to a predetermined number of bits.
Claim 16
Dependent Claim
66 words
The circuit of claim 14 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2 - (N+k) where N is equal to the number of bits of the radix of the quotient digit values and k is a predetermined number of guard bits, said second term being less than said first term.
Claim 17
Dependent Claim
23 words
The circuit of claim 14 wherein said reciprocal bias adjustment factor is equal to the sum of 2 -19 and 2 -22 .
Claim 18
Dependent Claim
124 words
The circuit of claim 1 wherein said circuitry for obtaining a short reciprocal comprises: look-up table circuitry for storing a plurality of short reciprocal values, each of said short reciprocal values comprising the truncated sum of an approximate reciprocal value and a reciprocal bias adjustment factor chosen to offset error in said approximate reciprocal value and bias said short reciprocal value to produce quotient digit values which, when accumulated to form a partial quotient, are always at most one unit in the last place greater than or exactly equal to an infinitely precise value of the quotient truncated to a predetermined number of bits; and retrieval circuitry coupled to said look-up table circuitry for retrieving a particular approximate reciprocal value associated with said divisor.
Claim 19
Dependent Claim
66 words
The circuit of claim 17 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2 - (N+k) where N is equal to the number of bits of the radix of the quotient digit values and k is a predetermined number of guard bits, said second term being less than said first term.
Claim 20
Dependent Claim
23 words
The circuit of claim 17 wherein said reciprocal bias adjustment factor is equal to the sum of 2 -19 and 2 -22 .
Claim 21
Dependent Claim
87 words
The circuit of claim 1 wherein said circuitry for obtaining a short reciprocal comprises: look-up table circuitry for storing a plurality of reciprocal seed values; retrieval circuitry for retrieving a particular reciprocal seed value associated with said divisor; circuitry associated with said retrieval circuitry for computing a first term comprising the difference between two and the product of said divisor and said particular reciprocal seed value and for computing a product of said first term and said particular reciprocal seed value to yield an approximate reciprocal value.
Claim 22
Dependent Claim
97 words
The circuit of claim 20 wherein said circuitry for obtaining a short reciprocal further comprises: circuitry for adding a reciprocal bias adjustment factor to said approximate reciprocal value to yield a sum and truncating said sum to yield said short reciprocal, said reciprocal bias adjustment factor chosen to offset error in said approximate reciprocal to product quotient digit values which, when accumulated to form a partial quotient, are always at most one unit in the last place greater than or exactly equal to an infinitely precise value of the quotient truncated to a predetermined number of bits.
Claim 23
Dependent Claim
66 words
The circuit of claim 21 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2 - (N+k) where N is equal to the number of bits of the radix of the quotient digit values and k is a predetermined number of guard bits, said second term being less than said first term.
Claim 24
Dependent Claim
23 words
The circuit of claim 21 wherein said reciprocal bias adjustment factor is equal to the sum of 2 -19 and 2 -22 .
Claim 25
Dependent Claim
114 words
The circuit of claim 1 wherein said circuitry for obtaining a short reciprocal comprises: circuitry for obtaining an approximate reciprocal value associated with said divisor; and circuitry for adding a reciprocal bias adjustment factor to said approximate reciprocal value to yield a sum and truncating said sum to yield said short reciprocal, said reciprocal bias adjustment factor chosen to offset error in said approximate reciprocal value and bias said short reciprocal to produce quotient digit values which, when accumulated to form a partial quotient, are always at most one unit in the last place greater than or exactly equal to an infinitely precise value of the quotient truncated to a predetermined number of bits.
Claim 26
Dependent Claim
66 words
The circuit of claim 24 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2 - (N+k) where N is equal to the number of bits of the radix of the quotient digit values and k is a predetermined number of guard bits, said second term being less than said first term.
Claim 27
Dependent Claim
23 words
The circuit of claim 24 wherein said reciprocal bias adjustment factor is equal to the sum of 2 -19 and 2 -22 .
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-09-02 | 1995-03-04 | 1995-09-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-09-02 | 1999-03-04 | 1999-09-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-09-02 | 2003-03-04 | 2003-09-03 | $7700.00 | Window Closed / Lapsed |