Division Algorithm - Division By A Constant

Division By A Constant

Division by a constant is equivalent to multiplication by its reciprocal. Since the denominator D is constant, so is its reciprocal (1/D). Thus it is possible to compute the value of (1/D) once at compile time, and at run time perform the multiplication N·(1/D) rather than the division N/D. In floating point arithmetic the use of (1/D) presents no problem, but in integer the reciprocal will always evaluate to zero, assuming |D| > 1.

Note that it is not necessary to use specifically (1/D), as any value (X/Y) that reduces to the same is equivalent. For example, for division by 3 you could multiply by 1/3, 2/6, 3/9, or 194/582. This way, you can choose Y to be any power of two, and replace the division step with a fast right bit shift. The effect of calculating N/D as (N·X)/Y is replacing a division by a multiply and a shift. Note that the parentheses are important, as N·(X/Y) will evaluate to zero.

However, unless D itself is a power of two, there is no X and Y that satisfies the conditions above. But it is not necessary for (X/Y) to be exactly equal to 1/D, only that it is "close enough" and such that the error introduced by this approximation is in the bits that are discarded by the shift operation. For further details see the reference.

As a concrete example, for 32 bit unsigned integers, division by 3 can be replaced with a multiply by, a multiplication by 2863311531 followed by a 33 right bit shift. This value is equal to .

In some cases, division by a constant can be accomplished in even less time by converting the "multiply by a constant" into a series of shifts and adds or subtracts. Of particular interest is division by 10, for which the exact quotient is obtained, with remainder if required.