论文标题
常数的整数划分：最佳界限
Integer Division by Constants: Optimal Bounds
论文作者
论文摘要
分数n的数字n的整数划分给出了商Q和剩余的r。通过将d替换为方便的整数C和m，通过M通过m的c * n（或c * n + c）替换n的d分割来加速编译器的软件，以使它们近似倒数：c/m〜 = 1/d。当选择M作为两个功率并且D是常数时，因此可以预先计算C和M时，此类技术尤其有利。文献在c/m和除数d之间的距离上包含许多界限。其中一些范围是最佳的，而另一些则不是。我们为商和剩余计算提供最佳的紧密界限。
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 ~= 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.
