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.
Read more about this topic: Division Algorithm
Famous quotes containing the words division and/or constant:
“If the technology cannot shoulder the entire burden of strategic change, it nevertheless can set into motion a series of dynamics that present an important challenge to imperative control and the industrial division of labor. The more blurred the distinction between what workers know and what managers know, the more fragile and pointless any traditional relationships of domination and subordination between them will become.”
—Shoshana Zuboff (b. 1951)
“Praise to Christ who feeds the hungry, frees the captive, finds the lost,
Heals the sick, upsets religion, fearless both of fate and cost.
Celebrate Christ’s constant presence—Friend and Stranger, Guest and Host.”
—The Iona Community (founded 1938)