An Analysis of Associated Dividends in the DBM Algorithm for Division by Constants Using Multiplication
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.
integer division division by multiplication multiplicative inverse dividend distribution