Integer division by constants: optimal bounds. Issue 6 (June 2021)

• Record Type: Journal Article
• Authors: Lemire, Daniel; Bartlett, Colin; Kaser, Owen
• Is Part Of: Heliyon. Volume 7:Issue 6(2021)
• Publication Date: 2021-06
• Subjects: Integer division -- Compiler optimization -- Tight bounds; Research -- Periodicals; Medical sciences -- Periodicals; Natural history -- Periodicals; Social sciences -- Periodicals; Earth sciences -- Periodicals; Physical sciences -- Periodicals; 507.2
• DOI: 10.1016/j.heliyon.2021.e07442
• Languages: English
• ISSNs: 2405-8440

Abstract

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. We present optimally tight bounds for quotient and remainder computations. Highlights: Generalizes theory on how to replace a division by a multiplication followed by a shift. Includes both the computation of the quotient and remainder. Introduces several new tighter bounds. Abstract : Integer division; Compiler optimization; Tight bounds