Patent US5258944A successfully refreshed from Google Patents.
US5258944A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High performance mantissa divider
Assignee: Silicon Graphics International Corp
•
Filing: 1992-09-01
•
Granted: 1993-11-02
•
Expires: 2012-09-01
Abstract
Abstract A high performance floating point mantissa divider employs SRT division, a Radix-4 redundant digit set and the principles of carry-save addition. At each step in the division, the upper few most significant bits of the partial remainder and the divisor are inspected via a look-up table to select the appropriate quotient digits. The quotient digits are represented in a Radix-4 redundant digit set, and the look-up table is generated using SRT division principles. The selected quotient digit is used to control a multiplexor which selects the selected multiple of the divisor. This value is subtracted from the partial remainder via a carry-save adder to form the new partial remainder. As the quotient digits are generated, they are placed in two shift registers, one for the sum digits and one for carry digits. When the division is complete, the shift registers are added to give the final quotient mantissa. A combination of a carry save adder and carry look ahead adder reduce the practical implementation to only 8 logic levels.
Inventors
- 👤 James E. Smith
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 05:17
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/48; G06F7/52; G06F7/535; G06F7/537; G06F7/5375; G06F7/483; G06F7/487; G06F7/4873; G06F7/499; G06F7/49942; G06F7/49947
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
338 words
An apparatus for performing division, comprising; first register means for storing a plurality of the least significant bits of a partial remainder and for sourcing a previous sum/carry partial remainder; second register means for storing a plurality of the most significant bits of the partial remainder, and for sourcing a previous assimilated partial remainder; multiplexor means, coupled to receive a divisor and coupled to receive a predicted next quotient, for selecting a divisor multiple and producing therefrom a selected divisor multiple; first adder means coupled to receive the previous sum/carry partial remainder and coupled to receive the selected divisor multiple, said first adder means for adding the previous sum/carry partial remainder and the selected divisor multiple and producing therefrom a next sum/carry partial remainder; second adder means coupled to receive a plurality of the bits of the previous sum/carry partial remainder, coupled to receive a plurality of the bits of the previous assimilated partial remainder, and coupled to receive a plurality of the bits of the selected divisor multiple, said second adder means for adding a plurality of the upper bits of the selected divisor multiple to a plurality of the upper bits of the previous assimilated partial remainder and to a plurality upper bits of the previous sum/carry partial remainder and producing therefrom a next assimilated partial remainder; third adder means coupled to receive the previous assimilated partial remainder and coupled to receive a plurality of the bits of the selected divisor multiple, said third adder means for adding a plurality of the upper bits of the selected divisor multiple to a plurality of the upper bits of the previous assimilated partial remainder and producing therefrom a plurality of the upper bits of a next partial remainder; and a quotient select circuit adapted to produce the predicted next quotient under control of the plurality of the upper bits of the next partial remainder and a plurality of the most significant bits of the divisor, and having an output operatively coupled to an input of said multiplexor means.
Claim 2
Independent Claim
338 words
An apparatus for performing division, comprising; first register means for storing a plurality of the least significant bits of a partial remainder and for sourcing a previous sum/carry partial remainder; second register means for storing a plurality of the most significant bits of the partial remainder, and for sourcing a previous assimilated partial remainder; multiplexor means, coupled to receive a divisor and coupled to receive a predicted next quotient, for selecting a divisor multiple and producing therefrom a selected divisor multiple; first adder means coupled to receive the previous sum/carry partial remainder and coupled to receive the selected divisor multiple, said first adder means for adding the previous sum/carry partial remainder and the selected divisor multiple and producing therefrom a next sum/carry partial remainder; second adder means coupled to receive a plurality of the bits of the previous sum/carry partial remainder, coupled to receive a plurality of the bits of the previous assimilated partial remainder, and coupled to receive a plurality of the bits of the selected divisor multiple, said second adder means for adding a plurality of the upper bits of the selected divisor multiple to a plurality of the upper bits of the previous assimilated partial remainder and to a plurality upper bits of the previous sum/carry partial remainder and producing therefrom a next assimilated partial remainder; third adder means coupled to receive the previous assimilated partial remainder and coupled to receive a plurality of the bits of the selected divisor multiple, said third adder means for adding a plurality of the upper bits of the selected divisor multiple to a plurality of the upper bits of the previous assimilated partial remainder and producing therefrom a plurality of the upper bits of a next partial remainder; and a quotient select circuit adapted to produce the predicted next quotient under control of the plurality of the upper bits of the next partial remainder and a plurality of the most significant bits of the divisor, and having an output operatively coupled to an input of said multiplexor means.
Claim 3
Dependent Claim
15 words
The apparatus of claim 1 wherein said first adder means includes a carry save adder.
Claim 4
Dependent Claim
18 words
The apparatus of claim 1 wherein said second and third adder means each include a carry lookahead adder.
Claim 5
Dependent Claim
16 words
The apparatus of claim 1 wherein said quotient select circuit includes a quotient select look-up table.
Claim 6
Dependent Claim
52 words
The apparatus of claim 2 wherein said carry save adder ripple carries two adjacent bits of the previous sum/carry partial remainder and of the selected divisor multiple to form two sum bits and a single carry bit of the partial remainder to produce therefrom a partial remainder in sum and carry form.
Claim 7
Dependent Claim
23 words
The apparatus of claim 1 further including: exponent subtract means for producing a quotient exponent; and sign means for producing a quotient sign.
Claim 8
Dependent Claim
21 words
The apparatus of claim 1 further including: quotient register means for storing the predicted next quotient in sum and carry form.
Claim 9
Dependent Claim
36 words
The apparatus of claim 7 further including adder means, connected to receive the predicted next quotient in sum and carry form, for adding quotient sums and quotient carries and producing therefrom a quotient in assimilated form.
Claim 10
Independent Claim
288 words
An apparatus for performing division, comprising: first register means for storing a plurality of the least significant bits of a partial remainder and for sourcing a previous sum/carry partial remainder; second register means for storing a plurality of the most significant bits of the partial remainder and for sourcing a previous assimilated partial remainder; multiplexor means, coupled to receive a divisor, for selecting a divisor multiple and producing therefrom a selected divisor multiple; adder means, including a carry save adder, coupled to receive the previous sum/carry partial remainder, coupled to receive the previous assimilated partial remainder, and coupled to receive the selected divisor multiple, and having a first output operatively coupled to an input of said first register means, a second output operatively coupled to an input of said second register means, said adder means for: adding a plurality of the most significant bits of the selected divisor multiple to the previous assimilated partial remainder, and to a plurality of the most significant bits of the previous sum/carry partial remainder to produce a next assimilated partial remainder, adding a plurality of the most significant bits of the selected divisor multiple to a plurality of the most significant bits of the previous assimilated partial remainder to produce a plurality of the most significant bits of a next partial remainder, and adding the previous sum/carry partial remainder and the selected divisor multiple to produce the next sum/carry partial remainder; and table means, coupled to receive the plurality of the most significant bits of the next partial remainder and coupled to receive a plurality of the most significant bits of the divisor, and having an output operatively coupled to an input of said multiplexor means, for producing a predicted next quotient.
Claim 11
Independent Claim
288 words
An apparatus for performing division, comprising: first register means for storing a plurality of the least significant bits of a partial remainder and for sourcing a previous sum/carry partial remainder; second register means for storing a plurality of the most significant bits of the partial remainder and for sourcing a previous assimilated partial remainder; multiplexor means, coupled to receive a divisor, for selecting a divisor multiple and producing therefrom a selected divisor multiple; adder means, including a carry save adder, coupled to receive the previous sum/carry partial remainder, coupled to receive the previous assimilated partial remainder, and coupled to receive the selected divisor multiple, and having a first output operatively coupled to an input of said first register means, a second output operatively coupled to an input of said second register means, said adder means for: adding a plurality of the most significant bits of the selected divisor multiple to the previous assimilated partial remainder, and to a plurality of the most significant bits of the previous sum/carry partial remainder to produce a next assimilated partial remainder, adding a plurality of the most significant bits of the selected divisor multiple to a plurality of the most significant bits of the previous assimilated partial remainder to produce a plurality of the most significant bits of a next partial remainder, and adding the previous sum/carry partial remainder and the selected divisor multiple to produce the next sum/carry partial remainder; and table means, coupled to receive the plurality of the most significant bits of the next partial remainder and coupled to receive a plurality of the most significant bits of the divisor, and having an output operatively coupled to an input of said multiplexor means, for producing a predicted next quotient.
Claim 12
Dependent Claim
17 words
The apparatus of claim 9 wherein the selected divisor multiple is dependent on the predicted next quotient.
Claim 13
Independent Claim
241 words
An apparatus for performing division in a computing machine, comprising: input means for receiving a divisor and a dividend; a selector coupled to receive the divisor and connected for selecting a divisor multiple under control of a predicted next quotient; a sum/carry partial remainder register connected to the input means to receive and store a first portion of a partial remainder in sum and carry form; an assimilated partial remainder register connected to the input means to receive and store a second portion of the partial remainder in assimilated form; a carry save adder coupled to an output of said sum/carry partial remainder register, coupled to an output of said selector and having an output coupled to an input of said sum/carry partial remainder register; a first carry lookahead adder coupled to an output of said assimilated partial remainder register, coupled to an output of said sum/carry partial remainder register, and coupled to an output of said selector, and having an output coupled to an input of said assimilated partial remainder register; a second carry lookahead adder coupled to an output of said assimilated partial remainder register and coupled to an output of said selector; and a predicted next quotient look-up table coupled to an output of said second carry look-ahead adder and coupled to said input means to receive a plurality of the most significant bits of the divisor, and having an output coupled to an input of said selector.
Claim 14
Independent Claim
241 words
An apparatus for performing division in a computing machine, comprising: input means for receiving a divisor and a dividend; a selector coupled to receive the divisor and connected for selecting a divisor multiple under control of a predicted next quotient; a sum/carry partial remainder register connected to the input means to receive and store a first portion of a partial remainder in sum and carry form; an assimilated partial remainder register connected to the input means to receive and store a second portion of the partial remainder in assimilated form; a carry save adder coupled to an output of said sum/carry partial remainder register, coupled to an output of said selector and having an output coupled to an input of said sum/carry partial remainder register; a first carry lookahead adder coupled to an output of said assimilated partial remainder register, coupled to an output of said sum/carry partial remainder register, and coupled to an output of said selector, and having an output coupled to an input of said assimilated partial remainder register; a second carry lookahead adder coupled to an output of said assimilated partial remainder register and coupled to an output of said selector; and a predicted next quotient look-up table coupled to an output of said second carry look-ahead adder and coupled to said input means to receive a plurality of the most significant bits of the divisor, and having an output coupled to an input of said selector.
References Cited (Backward Citations)
US3733477A
Cited
US4546447A
Cited
US4939686A
Cited
US5132925A
Cited
US4979142A
Cited
US5128891A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-11-01 | 1997-05-03 | 1997-11-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-11-01 | 2001-05-03 | 2001-11-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-11-01 | 2005-05-03 | 2005-11-02 | $7700.00 | Window Closed / Lapsed |