High precision integer division using low precision hardware operations and rounding techniques

• US 8,655,937 B1
• Filed: 04/29/2009
• Issued: 02/18/2014
• Est. Priority Date: 04/29/2009
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Vanderspek, Julius
• Primary Examiner(s): Tsai, Henry
• Assistant Examiner(s): Hassan, Aurangzeb
• Application Number:
  US12/432,064
• Time in Patent Office: 1,756 Days
• Field of Search: None
• US Class Current: 708/650
• CPC Class Codes: G06F 2207/5351 Multiplicative non-restoring division, e.g. SRT, using multiplication in quotient selection
• CPC Class Codes: G06F 7/4873 Dividing
• CPC Class Codes: G06F 7/535 Dividing only

Abstract

One or more embodiments of the invention set forth techniques to perform integer division using a floating point hardware unit supporting floating point variables of a certain bit size. The numerator and denominator are integers having a bit size that is greater than the bit size of the floating point variables supported by the floating point hardware unit. Error correcting techniques are utilized to account for any loss of precision caused by the floating point operations.

Claims

1. A computer-implemented method for performing integer division between a numerator and a denominator on a processing unit that supports operations using variables of a first bit size, wherein the numerator and the denominator are integers having a second bit size that is greater than the first bit size, the method comprising:

subdividing the numerator into a plurality of equal sized partitions, wherein each partition has a third bit size;

converting the denominator into a variable of the first bit size;

dividing the numerator by the variable of the first bit size to obtain a current approximation of a current portion of a quotient, wherein the current approximation of the current portion of the quotient has the third bit size;

subtracting a product of the current approximation of the current portion of the quotient and the denominator from the numerator to generate a subsequent numerator, wherein a fourth bit size of most significant bits associated with the subsequent numerator represents a bit overflow error value utilized to correct the first approximation of the first portion of the quotient; and

storing the current approximation of the current portion of the quotient in a memory.

2. The method of claim 1, further comprising the steps of:

dividing the subsequent numerator by the variable of the first bit size to obtain a subsequent approximation of a subsequent portion of the quotient that has a bit size equal to the third bit size plus the fourth bit size;

adding a number of most significant bits equal to the fourth bit size associated with the subsequent approximation to a number of least significant bits equal to the fourth bit size associated with the current approximation to generate a corrected current approximation of the current portion of the quotient;

multiplying the subsequent approximation of the subsequent portion of the quotient with the denominator to obtain a product; and

subtracting the product from the subsequent numerator to generate a next numerator, wherein the fourth bit size of most significant bits associated with the next numerator represents a bit overflow error value utilized to correct the subsequent approximation of the subsequent portion of the quotient.

3. The method of claim 2, wherein the steps of dividing, adding, multiplying and subtracting in claim 2 are repeated, wherein, for each current iteration of the dividing, adding, multiplying and subtracting steps, the next numerator generated in the subtracting step of the immediately preceding iteration is used as the subsequent numerator in the dividing step of the current iteration, the subsequent approximation obtained in the dividing step of the current iteration is used as the subsequent approximation in the adding step of the current iteration, and the subsequent approximation obtained in the dividing step of the immediately preceding iteration is used as the current approximation of the adding step of the current iteration, until a total number of corrected approximations of portions of the quotient have been generated equal to the number of equal sized partitions included in the plurality of equal sized partitions.

4. The method of claim 3, further comprising adding one to a final quotient to compensate for a final bit overflow error value of a last iteration.

5. The method of claim 1, wherein the dividing step is performed by a floating point hardware unit and the supported variables of the first bit size are floating point variables that have mantissas of a fifth bit size.

6. The method of claim 5, wherein the third bit size is less than the fifth bit size.

7. The method of claim 6, wherein the first bit size is 32, the second bit size is 64, the third bit size is 16 and the fourth bit size is 2.

8. A non-transitory computer-readable medium including instructions that, when executed by a processing unit that supports operations using variables of a first bit size, causes the processing unit to perform integer division between a numerator and a denominator, wherein the numerator and the denominator are integers having a second bit size that is greater than the first bit size, by performing the steps of:

subdividing the numerator into a plurality of equal sized partitions, wherein each partition has a third bit size;

converting the denominator into a variable of the first bit size;

dividing the numerator by the variable of the first bit size to obtain a current approximation of a current portion of a quotient, wherein the current approximation of the current portion of the quotient has the third bit size;

subtracting a product of the current approximation of the current portion of the quotient and the denominator from the numerator to generate a subsequent numerator, wherein a fourth bit size of most significant bits associated with the subsequent numerator represents a bit overflow error value utilized to correct the first approximation of the first portion of the quotient; and

storing the current approximation of the current portion of the quotient in a memory.

9. The non-transitory computer-readable medium of claim 8, wherein the processing unit further performs the steps:

dividing the subsequent numerator by the variable of the first bit size to obtain a subsequent approximation of a subsequent portion of the quotient that has a bit size equal to the third bit size plus the fourth bit size;

adding a number of most significant bits equal to the fourth bit size associated with the subsequent approximation to a number of least significant bits equal to the fourth bit size associated with the current approximation to generate a corrected current approximation of the current portion of the quotient;

multiplying the subsequent approximation of the subsequent portion of the quotient with the denominator to obtain a product; and

subtracting the product from the subsequent numerator to generate a next numerator, wherein the fourth bit size of most significant bits associated with the next numerator represents a bit overflow error value utilized to correct the subsequent approximation of the subsequent portion of the quotient.

10. The non-transitory computer-readable medium of claim 9, wherein the steps of dividing, adding, multiplying and subtracting in claim 9 are repeated, wherein, for each current iteration of the dividing, adding, multiplying and subtracting steps, the next numerator generated in the subtracting step of the immediately preceding iteration is used as the subsequent numerator in the dividing step of the current iteration, the subsequent approximation obtained in the dividing step of the current iteration is used as the subsequent approximation in the adding step of the current iteration, and the subsequent approximation obtained in the dividing step of the immediately preceding iteration is used as the current approximation of the adding step of the current iteration, until a total number of corrected approximations of portions of the quotient have been generated equal to the number of equal sized partitions included in the plurality of equal sized partitions.

11. The non-transitory computer-readable medium of claim 10, wherein the processing unit further performs the step of adding one to a final quotient to compensate for a final bit overflow error value of a last iteration.

12. The non-transitory computer-readable medium of claim 11, wherein the third bit size is less than the fifth bit size.

13. The computer-readable medium of claim 8, wherein the dividing step is performed by a floating point hardware unit and the supported variables of the first bit size are floating point variables that have mantissas of a fifth bit size.

14. The non-transitory computer-readable medium of claim 13, wherein the first bit size is 32, the second bit size is 64, the third bit size is 16 and the fourth bit size is 2.

15. A computing system configured to perform integer division between a numerator and a denominator on a processing unit that supports operation using variables of a first bit size, wherein the numerator and the denominator are integers having a second bit size that is greater than the first bit size, the computer system comprising:

a system memory configured to store a code segment containing the integer division and a compiler; and

a processor coupled to the system memory, wherein the processor is configured to execute the compiler to perform the steps of;

subdividing the numerator into a plurality of equal sized partitions, wherein each partition has a third bit size, converting the denominator into a variable of the first bit size, dividing the numerator by the variable of the first bit size to obtain a current approximation of a current portion of a quotient, wherein the current approximation of the current portion of the quotient has the third bit size, subtracting a product of the current approximation of the current portion of the quotient and the denominator from the numerator to generate a subsequent numerator, wherein a fourth bit size of most significant bits associated with the subsequent numerator represents a bit overflow error value utilized to correct the first approximation of the first portion of the quotient, and storing the current approximation of the current portion of the quotient in a memory.

16. The computing system of claim 15, wherein the processor further performs the steps:

dividing the subsequent numerator by the variable of the first bit size to obtain a subsequent approximation of a subsequent portion of the quotient that has a bit size equal to the third bit size plus the fourth bit size;

adding a number of most significant bits equal to the fourth bit size associated with the subsequent approximation to a number of least significant bits equal to the fourth bit size associated with the current approximation to generate a corrected current approximation of the current portion of the quotient;

multiplying the subsequent approximation of the subsequent portion of the quotient with the denominator to obtain a product; and

subtracting the product from the subsequent numerator to generate a next numerator, wherein the fourth bit size of most significant bits associated with the next numerator represents a bit overflow error value utilized to correct the subsequent approximation of the subsequent portion of the quotient.

17. The computing system of claim 16, wherein the steps of dividing, adding, multiplying and subtracting in claim 16 are repeated, wherein, for each current iteration of the dividing, adding, multiplying and subtracting steps, the next numerator generated in the subtracting step of the immediately preceding iteration is used as the subsequent numerator in the dividing step of the current iteration, the subsequent approximation obtained in the dividing step of the current iteration is used as the subsequent approximation in the adding step of the current iteration, and the subsequent approximation obtained in the dividing step of the immediately preceding iteration is used as the current approximation of the adding step of the current iteration, until a total number of corrected approximations of portions of the quotient have been generated equal to the number of equal sized partitions included in the plurality of equal sized partitions.

18. The computing system of claim 15, wherein the processor further performs the step of adding one to a final quotient to compensate for a final bit overflow error value of a last iteration.

19. The computing system of claim 15, wherein the dividing step is performed by a floating point hardware unit and the supported variables of the first bit size are floating point variables that have mantissas of a fifth bit size.

20. The computing system of claim 15, wherein the third bit size is less than the fifth bit size.