Integer division using floating-point reciprocal

摘要

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.

主权项

1. 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.