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 [Formula: see text] (or [Formula: see text]) by m for convenient integers c and m chosen so that they approximate the reciprocal: [Formula: see text]. 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 [Formula: see text] 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.