US 5,128,891 AGranted

High speed divider with square root capability

AssigneeAdvanced Micro Devices, Inc.

InventorsThomas W. Lynch, Stephen D. McIntyre, Ken Tseng, Salim A. Shah, Tony Hurson

Life of this patent

Estimating the term…

Loading patent…

Abstract

An apparatus for performing the division of a first operand by a second operand by iteratively producing a series of partial remainders and predicted quotient bits utilizing the generation of multiples of the second operand and the selection of one of the generated multiples. The second operand is first selected as a first partial remainder. A first quotient bit is predicted from the first and second operands and a next quotient bit is predicted from the partial remainder and the second operand. One of the generated multiples is selected for producing a next partial remainder based upon the next quotient prediction. A next partial remainder is then produced from the produced partial remainder and the selected multiple of the second operand.

Claims33

Dependent claims

Apparatus for performing a division of a first operand by a second operand to produce a result comprised of a series of quotient bits, comprising:

means for iteratively producing a series of partial remainders, said means for iteratively producing a series of partial remainders selecting said first operand as a first partial remainder;
means for iteratively predicting a series of quotient bits, said quotient prediction means predicting a first quotient bit based upon said first operand and said second operand, and a next quotient bit based upon one of said series of partial remainders and said second operand;
a first quotient register connected to said quotient prediction logic to receive and store said next quotient bit determined by said quotient prediction logic;
a second quotient register connected to said quotient prediction logic to receive said next quotient bit and store said next quotient bit minus one;
means for generating multiples of said second operand;
said means for iteratively producing a series of partial remainders determining a next partial remainder based upon one of said series of produced partial remainders and one of said multiples of said second operand;
said means for iteratively producing a series of partial remainders further including means for selecting, based upon said next quotient bit, one of said generated multiples of said second operand for producing said next partial remainder.

4 more elements

An apparatus for dividing a dividend by a divisor to produce a result, comprising:

a partial remainder register connected to receive and store said dividend as a partial remainder;
a divisor register connected to receive and store said divisor;
quotient prediction logic connected to receive said divisor from said divisor register and said partial remainder from said partial remainder register, said quotient prediction logic determining a quotient bit based upon said received divisor and partial remainder;
a first quotient register connected to receive and store said quotient bit determined by said quotient prediction logic;
means, connected to said divisor register, for generating multiples of said divisor;
and
a carry save adder connected to receive said multiples of said divisor from said means for generating multiples of said divisor and said predicted quotient bit from said quotient prediction logic, said carry save adder determining a next partial remainder by selecting one of said multiples of said divisor and adding it to said partial remainder, said partial remainder register connected to receive and store said next partial remainder in place of said partial remainder, said quotient prediction logic connected to receive said next partial remainder to determine a next quotient bit.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 07/504,324Filed 2 Apr 1990
Granted: 7 Jul 1992
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 7/535
Multiplying; Dividing: dividing only
G06F 7/5375
Reduction of the number of iteration steps or stages, e.g. using the Sweeny-Robertson-Tocher [SRT] algorithm: non restoring calculation, where…
G06F 7/5525
Powers or roots , e.g. Pythagorean sums: roots or inverse roots of single operands
G06F 2207/5528
Roots or inverse roots of single operands: non-restoring calculation, where each result digit is either negative, zero or positive, e.g. SRT