Open access research
publication repository

Integer Division by Constants: Optimal Bounds [r-libre/2438]

Lemire, Daniel; Bartlett, Colin, & Kaser, Owen (2021). Integer Division by Constants: Optimal Bounds. Heliyon, 7 (6). https://doi.org/10.1016/j.heliyon.2021.e07442

File(s) available for this item:
[img]  PDF - 2012.12369.pdf
Content : Submitted Version
License : Creative Commons Attribution.
Item Type: Journal Articles
Refereed: Yes
Status: Published
Abstract: 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. Using accessible mathematics, we present optimally tight bounds for quotient and remainder computations.
Official URL: https://www.sciencedirect.com/science/article/pii/...
Depositor: Lemire, Daniel
Owner / Manager: Daniel Lemire
Deposited: 15 Nov 2021 16:50
Last Modified: 15 Nov 2021 16:50

Actions (login required)