Division and root computation with fast result formatting

Patent metadata

Field	Value
Publication number	US-9753694-B2
Application number	US-201514692071-A
Country	US
Kind code	B2
Filing date	Apr 21, 2015
Priority date	Apr 21, 2015
Publication date	Sep 5, 2017
Grant date	Sep 5, 2017

Abstract

Systems and methods relate to division of a dividend by a divisor, with fast result formatting. Counts of leading sign bits of the dividend and the divisor are determined. The dividend and the divisor are normalized based on their respective counts of leading sign bits to obtain a normalized dividend and a normalized divisor, respectively. An exact number of significant quotient bits of a quotient of the division, based on the normalized dividend, the normalized divisor, and the counts of leading sign bits of the dividend and the divisor and used to determine a correct position of a leading bit of the quotient based on this exact number. The quotient is developed by placing the leading bit at or near the correct position and appending less significant bits to the right of the leading bit. Thus, left-shifts in each iteration and large final shifts are avoided in formatting the result.

First claim

What is claimed is:

1. An apparatus configured to perform division of a dividend with a divisor, the apparatus comprising:
leading sign counters to count leading sign bits of the dividend and the divisor;
normalizers to normalize the dividend and the divisor based on their respective counts of leading sign bits and generate a normalized dividend and a normalized divisor, respectively;
logic to determine an exact number of significant quotient bits of a quotient of the division, based on the normalized dividend, the normalized divisor, and the counts of leading sign bits of the dividend and the divisor;
logic to determine a correct position of a leading bit of the quotient based on the exact number of significant quotient bits; and
logic to develop the quotient with the leading bit placed at or near the correct position and less significant bits appended to the right of the leading bit.

2. The apparatus of claim 1 , wherein the logic to determine the correct position of the leading bit of the quotient comprises a divide-by-r module to determine a number of quotient groups to hold the exact number of significant quotient bits, based on the exact number of significant quotient bits and a radix of the division, each quotient group comprising a number r of two or more bits.

3. The apparatus of claim 2 , wherein the logic to develop the quotient further comprises an iterator to iteratively develop the quotient, one quotient group per iteration.

4. The apparatus of claim 3 , wherein the iterator comprises at least part of a floating point divider.

5. The apparatus of claim 3 , wherein the logic to develop the quotient further comprises an array of n quotient registers to receive bits of the quotient from the iterator, wherein a first quotient register of the array is configured to store a first quotient group comprising the leading bit when an enable corresponding to the first quotient register is set.

6. The apparatus of claim 5 , wherein the logic to develop the quotient further comprises a finite state machine (FSM) to selectively set the enable corresponding to the first quotient register in the first iteration.

7. The apparatus of claim 5 , wherein a second register of the array is configured to store a second quotient group comprising quotient bits less significant than quotient bits of the first quotient group, wherein the second quotient register is located to the right of the first quotient register in the array of n quotient registers.

8. The apparatus of claim 2 , wherein the logic to determine the correct position of the leading bit of the quotient comprises a shift module to shift a concatenated result from the number of quotient groups by up to r−1 bits to form the quotient.

9. The apparatus of claim 8 , wherein the quotient is a normalized floating point number or a subnormal floating point number.

10. The apparatus of claim 1 , wherein the dividend and the divisor are integers.

11. The apparatus of claim 1 , wherein the logic to determine an exact number of significant quotient bits comprises
a subtraction module to determine a difference between the count of leading sign bits of the dividend and the count of the leading sign bits of the divisor plus one; and
a compare module to compare the magnitude of the normalized dividend and the magnitude of the normalized divisor.

12. The apparatus of claim 1 , wherein the leading sign counters comprise leading zero counters and XOR circuits.

13. An apparatus for performing a division of a dividend by a divisor, the apparatus comprising:
means for determining counts of leading sign bits of the dividend and the divisor;
means for normalizing the dividend and the divisor based on their respective counts of leading sign bits to obtain a normalized dividend and a normalized divisor, respectively;
means for determining an exact number of significant quotient bits of a quotient of the division, based on the normalized dividend, the normalized divisor, and the counts of leading sign bits of the dividend and the divisor;
means for determining a correct position of a leading bit of the quotient based on the exact number of significant quotient bits; and
means for developing the quotient by placing the leading bit at or near the correct position and appending less significant bits to the right of the leading bit.

14. The apparatus of claim 13 , wherein the means for determining the correct position further comprises means for determining a number of quotient groups to hold the exact number of significant quotient bits, based on the exact number of significant quotient bits and a radix of the division, each quotient group comprising a number r of two or more bits; and means for iteratively developing the quotient by generating one quotient group per iteration.

Assignees

• Qualcomm Inc

Inventors

• Dockser Kenneth Alan
• Dibrino Michael Thomas
• Lall Pathik Sunil

Classifications

• G06F5/01

  for shifting, e.g. justifying, scaling, normalising {(digital stores in which the information is moved stepwise, e.g. shift-registers G11C19/00; digital stores in which the information circulates G11C21/00)} · CPC title

• G06F7/535 Primary

  Dividing only · CPC title

• G06F2207/535

  Indexing scheme relating to groups G06F7/535 - G06F7/5375 · CPC title

• G06F2205/003

  Reformatting, i.e. changing the format of data representation · CPC title

• G06F7/4873

  Dividing · CPC title