Integer division by constants: optimal bounds

The integer division of a numerator n by a divisor d gives a quotient q and a remainder r. Optimizing compilers accelerate software by replacing the division of n by d with the division of c * n (or c * n + c) by m for convenient integers c and m chosen so that they approximate the reciprocal: c/m approximate to 1/d. Such techniques are especially advantageous when m is chosen to be a power of two and when d is a constant so that c and m can be precomputed. The literature contains many bounds on the distance between c/m and the divisor d. Some of these bounds are optimally tight, while others are not. We present optimally tight bounds for quotient and remainder computations.

Automated summary

The paragraph discusses techniques for optimizing software by replacing integer division with more convenient calculations, such as transforming n divided by d into c*n (or c*n + c) divided by m, where c and m are chosen to approximate the reciprocal c/m to 1/d.