Répertoire de publications
de recherche en accès libre
de recherche en accès libre
Lemire, Daniel; Bartlett, Colin et Kaser, Owen (2021). Integer Division by Constants: Optimal Bounds. Heliyon, 7 (6). https://doi.org/10.1016/j.heliyon.2021.e07442
Fichier(s) associé(s) à ce document :![[img]](https://r-libre.teluq.ca/style/images/fileicons/pdf.png)
|
PDF
- 2012.12369.pdf
Contenu du fichier : Manuscrit soumis (avant évaluation) Licence : Creative Commons CC BY. |
|
| Catégorie de document : | Articles de revues |
|---|---|
| Évaluation par un comité de lecture : | Oui |
| Étape de publication : | Publié |
| Résumé : | 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. |
| Adresse de la version officielle : | https://www.sciencedirect.com/science/article/pii/... |
| Déposant: | Lemire, Daniel |
| Responsable : | Daniel Lemire |
| Dépôt : | 15 nov. 2021 16:50 |
| Dernière modification : | 15 nov. 2021 16:50 |
|
RÉVISER |
