Division by invariant integers using multiplication

摘要

Integer division remains expensive on today's processors as thecost of integer multiplication declines. We present code sequences fordivision by arbitrary nonzero integer constants and run-time invariantsusing integer multiplication. The algorithms assume a two's complementarchitecture. Most also require that the upper half of an integerproduct be quickly accessible. We treat unsigned division, signeddivision where the quotient rounds towards zero, signed division wherethe quotient rounds towards -∞, and division where the result is knowna priori to be exact. We give someimplementation results using the C compiler GCC.