An Analysis of Associated Dividends in the DBM Algorithm for Division by Constants Using Multiplication

Autor:	A. E. Werbrouck, Davide Cavagnino
Rok vydání:	2009
Předmět:	Discrete mathematics Multiplication algorithm General Computer Science Divisor Mathematics::Optimization and Control Inverse Short division Combinatorics Partition (number theory) Dividend Algorithm Quotient Multiple Mathematics
Zdroj:	The Computer Journal. 54:148-156
ISSN:	1460-2067 0010-4620
Popis:	When a compiler encounters a fixed integer divisor, which is not a power of 2, it can calculate its inverse to be multiplied by the run-time integer dividends to obtain the quotients, using our very efficient, recently published [Cavagnino, D. and Werbrouck, A.E. (2008) Efficient algorithms for integer division by constants using multiplication. Comp. J., 51, 470–480] division by multiplication algorithms. Essentially our algorithms permit a complete partition of a defined number space into non-adverse and adverse divisors on the basis of whether a dividend associated with each divisor is, or is not, greater than the maximum dividend size. In this paper, we demonstrate useful relations between the dividends associated with all divisors and with their multiples by positive powers of 2 leading to rapid iterative algorithms for calculating full sets of associated dividends.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::962809a9d90616b8a0c7a09d5e2a3ea9 https://doi.org/10.1093/comjnl/bxp117 Zobrazit plný text záznamu