Integer division using floating-point reciprocal
AssigneeNVIDIA Corporation
InventorJulius Vanderspek
Life of this patent
Estimating the term…
Abstract
One embodiment of the present invention sets forth a technique for performing fast integer division using commonly available arithmetic operations. The technique may be implemented in a four-stage process using a single-precision floating point reciprocal in conjunction with integer addition and multiplication. Furthermore, the technique may be fully pipelined on many conventional processors for overall performance that is comparable to the best available high-performance alternatives.
Claims22
A computer implemented method for performing integer division operations on a central processing unit (CPU), the method comprising:
- receiving an integer dividend and an integer divisor;
- computing a floating-point reciprocal based on the divisor;
- computing a lowered floating-point reciprocal based on the floating-point reciprocal, wherein the lowered floating-point reciprocal is lower than the floating-point reciprocal by up to two least significant bits of the mantissa of the floating-point reciprocal;
- computing, via an execution unit within the CPU, a lower bound quotient based on a product of the lowered floating-point reciprocal and a floating point variable assigned a value of the integer dividend, wherein the product is designated as an unsigned integer;
- generating a reduced error quotient based on the lower bound quotient;
- and
- correcting the reduced error quotient to generate a final quotient,
- wherein the CPU does not include any circuitry specifically configured to perform integer division operations.
A non-transitory computer-readable medium including instructions that, when executed by a processing unit, cause the processing unit to perform integer division operations, by performing the steps of:
- receiving an integer dividend and an integer divisor;
- computing a floating-point reciprocal based on the divisor;
- computing, via an execution unit within the processing unit, a lowered floating-point reciprocal based on the floating-point reciprocal, wherein the lowered floating-point reciprocal is lower than the floating-point reciprocal by up to two least significant bits of the mantissa of the floating-point reciprocal;
- computing a lower bound quotient based on a product of the lowered floating-point reciprocal and a floating point variable assigned a value of the integer dividend, wherein the product is designated as an unsigned integer;
- generating a reduced error quotient based on the lower bound quotient;
- and
- correcting the reduced error quotient to generate a final quotient,
- wherein the processing unit does not include any circuitry specifically configured to perform integer division operations.
A computing device configured perform integer division operations, the computing device comprising:
- a memory configured to store program instructions and program data;
- and
- a central processing unit (CPU) configured to execute the program instructions and perform the steps of:
- receiving an integer dividend and an integer divisor;
- computing a floating-point reciprocal based on the divisor;
- computing a lowered floating-point reciprocal based on the floating-point reciprocal, wherein the lowered floating-point reciprocal is lower than the floating-point reciprocal by up to two least significant bits of the mantissa of the floating-point reciprocal;
- computing, via an execution unit within the CPU, a lower bound quotient based on a product of the lowered floating-point reciprocal and a floating point variable assigned a value of the integer dividend, wherein the product is designated as an unsigned integer;
- generating a reduced error quotient based on the lower bound quotient;
- and
- correcting the reduced error quotient to generate a final quotient,
- wherein the CPU does not include any circuitry specifically configured to perform integer division operations.
Dependencies are inferred from the claim text.