Répertoire de publications
de recherche en accès libre
de recherche en accès libre
Lemire, Daniel; Kaser, Owen et Kurz, Nathan (2019). Faster Remainder by Direct Computation: Applications to Compilers and Software Libraries. Software: Practice and Experience, 49 (6), 953-970. https://doi.org/10.1002/spe.2689
Fichier(s) associé(s) à ce document :|
PDF
- Faster_Remainder_of_the_Division_by_a_Constant.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é : | On common processors, integer multiplication is many times faster than integer division. Dividing a numerator n by a divisor d is mathematically equivalent to multiplication by the inverse of the divisor (n / d = n x 1/d). If the divisor is known in advance---or if repeated integer divisions will be performed with the same divisor---it can be beneficial to substitute a less costly multiplication for an expensive division. Currently, the remainder of the division by a constant is computed from the quotient by a multiplication and a subtraction. But if just the remainder is desired and the quotient is unneeded, this may be suboptimal. We present a generally applicable algorithm to compute the remainder more directly. Specifically, we use the fractional portion of the product of the numerator and the inverse of the divisor. On this basis, we also present a new, simpler divisibility algorithm to detect nonzero remainders. We also derive new tight bounds on the precision required when representing the inverse of the divisor. Furthermore, we present simple C implementations that beat the optimized code produced by state-of-art C compilers on recent x64 processors (e.g., Intel Skylake and AMD Ryzen), sometimes by more than 25%. On all tested platforms including 64-bit ARM and POWER8, our divisibility-test functions are faster than state-of-the-art Granlund-Montgomery divisibility-test functions, sometimes by more than 50%. |
| Adresse de la version officielle : | https://onlinelibrary.wiley.com/doi/abs/10.1002/sp... |
| Déposant: | Lemire, Daniel |
| Responsable : | Daniel Lemire |
| Dépôt : | 21 févr. 2019 15:53 |
| Dernière modification : | 25 oct. 2019 20:43 |
|
RÉVISER |
