Cargando…

Integer division by constants: optimal bounds

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 [Formula: see text] (or [Formula: see text]) by m for convenient integers c and m chosen so that they approxima...

Descripción completa

Detalles Bibliográficos
Autores principales: Lemire, Daniel, Bartlett, Colin, Kaser, Owen
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Elsevier 2021
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8258644/
https://www.ncbi.nlm.nih.gov/pubmed/34307934
http://dx.doi.org/10.1016/j.heliyon.2021.e07442
_version_ 1783718537043378176
author Lemire, Daniel
Bartlett, Colin
Kaser, Owen
author_facet Lemire, Daniel
Bartlett, Colin
Kaser, Owen
author_sort Lemire, Daniel
collection PubMed
description 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 [Formula: see text] (or [Formula: see text]) by m for convenient integers c and m chosen so that they approximate the reciprocal: [Formula: see text]. 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 [Formula: see text] 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.
format Online
Article
Text
id pubmed-8258644
institution National Center for Biotechnology Information
language English
publishDate 2021
publisher Elsevier
record_format MEDLINE/PubMed
spelling pubmed-82586442021-07-23 Integer division by constants: optimal bounds Lemire, Daniel Bartlett, Colin Kaser, Owen Heliyon Research Article 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 [Formula: see text] (or [Formula: see text]) by m for convenient integers c and m chosen so that they approximate the reciprocal: [Formula: see text]. 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 [Formula: see text] 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. Elsevier 2021-06-29 /pmc/articles/PMC8258644/ /pubmed/34307934 http://dx.doi.org/10.1016/j.heliyon.2021.e07442 Text en © 2021 The Authors. Published by Elsevier Ltd. https://creativecommons.org/licenses/by/4.0/This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
spellingShingle Research Article
Lemire, Daniel
Bartlett, Colin
Kaser, Owen
Integer division by constants: optimal bounds
title Integer division by constants: optimal bounds
title_full Integer division by constants: optimal bounds
title_fullStr Integer division by constants: optimal bounds
title_full_unstemmed Integer division by constants: optimal bounds
title_short Integer division by constants: optimal bounds
title_sort integer division by constants: optimal bounds
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8258644/
https://www.ncbi.nlm.nih.gov/pubmed/34307934
http://dx.doi.org/10.1016/j.heliyon.2021.e07442
work_keys_str_mv AT lemiredaniel integerdivisionbyconstantsoptimalbounds
AT bartlettcolin integerdivisionbyconstantsoptimalbounds
AT kaserowen integerdivisionbyconstantsoptimalbounds