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:
“Between married persons, the cement of friendship is by the laws supposed so strong as to abolish all division of possessions: and has often, in reality, the force ascribed to it.
”
—David Hume (1711–1776)
“The East is the hearthside of America. Like any home, therefore, it has the defects of its virtues. Because it is a long-lived-in house, it bursts its seams, is inconvenient, needs constant refurbishing. And some of the family resources have been spent. To attain the privacy that grown-up people find so desirable, Easterners live a harder life than people elsewhere. Today it is we and not the frontiersman who must be rugged to survive.”
—Phyllis McGinley (1905–1978)