Division By A Constant
The division by a constant D is equivalent to the multiplication by its reciprocal. Since the denominator 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 little 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 (digital)
Famous quotes containing the words division and/or constant:
“Don’t order any black things. Rejoice in his memory; and be radiant: leave grief to the children. Wear violet and purple.... Be patient with the poor people who will snivel: they don’t know; and they think they will live for ever, which makes death a division instead of a bond.”
—George Bernard Shaw (1856–1950)
“Language is like soil. However rich, it is subject to erosion, and its fertility is constantly threatened by uses that exhaust its vitality. It needs constant re-invigoration if it is not to become arid and sterile.”
—Elizabeth Drew (1887–1965)