The multiplicative inverse of a divisor d can be used to test for a zero remainder after division by d [GM].
First, consider unsigned division with the divisor d odd. Denote by d?/span> the multiplicative inverse of d. Then, because dd?/span> 1 (mod 2W), where W is the machine's word size in bits, d?/span> is also odd. Thus, d?/span> is relatively prime to 2W, and as shown in the proof of theorem MI in the preceding section, as n ranges over all 2W distinct values modulo 2W, nd?/span> takes on all 2W distinct values modulo 2W.
It was shown in the preceding section that if n is a multiple of d,
That is, for Therefore, for n not a multiple of d, the value of nd?/span>, reduced modulo 2W to the range 0 to 2W - 1, must exceed
This can be used to test for a zero remainder. For example, to test if an integer n is a multiple of 25, multiply n by and compare the rightmost W bits to On our basic RISC:
li牋牋 M,0xC28F5C29?Load mult. inverse of 25.
mul牋?q,M,n牋牋牋牋 q = right half of M*n.
li牋牋 c,0x0A3D70A3?c = floor((2**32-1)/25).
cmpleu t,q,c牋牋牋牋 Compare q and c, and branch
bt牋牋 t,is_mult牋牋 if n is a multiple of 25.
To extend this to even divisors, let d = do ?2k, where do is odd and k 1. Then, because an integer is divisible by d if and only if it is divisible by do and by 2k, and because n and have the same number of trailing zeros ( is odd), the test that n is a multiple of d is
where the "mod" function is understood to reduce to the interval [0, 2W - 1]
Direct implementation of this requires two tests and conditional branches, but it can be reduced to one compare-branch quite efficiently if the machine has the rotate-shift instruction. This follows from the following theorem, in which denotes the computer word a rotated right k positions (0 k 32).
Proof. (Assume a 32-bit machine.) Suppose and x ends in k 0-bits. Then, because But Therefore, If x does not end in k 0-bits, then does not begin with k 0-bits, whereas Lastly, if and x ends in k 0-bits, then the integer formed from the first 32 - k bits of x must exceed that formed from the first 32 - k bits of a, so that
Using this theorem, the test that n is a multiple of d, where n and d 1 are unsigned integers and d = do ?2k with do odd, is
Here we used
As an example, the following code tests an unsigned integer n to see if it is a multiple of 100:
li牋牋 M,0xC28F5C29?Load mult. inverse of 25.
mul牋?q,M,n牋牋牋牋 q = right half of M*n.
shrri?q,q,2牋牋牋牋 Rotate right two positions.
li牋牋 c,x'028F5C28' c = floor((2**32-1)/100).
cmpleu t,q,c牋牋牋牋 Compare q and c, and branch
bt牋牋 t,is_mult牋牋 if n is a multiple of 100.
For signed division, it was shown in the preceding section that if n is a multiple of d, and d is odd, then
Thus, for we have Furthermore, because d?/span> is relatively prime to 2W, as n ranges over all 2W distinct values modulo 2W, nd?/span> takes on all 2W distinct values modulo 2W. Therefore, n is a multiple of d if and only if
where the "mod" function is understood to reduce nd?/span> to the interval [-2W - 1, 2W - 1 - 1].
This can be simplified a little by observing that because d is odd and, as we are assuming, positive and not equal to 1, it does not divide 2W - 1. Therefore,
Thus, for signed numbers, the test that n is a multiple of d, where d = do ?2k and do is odd, is
On the surface, this would seem to require three tests and branches. However, as in the unsigned case, it can be reduced to one compare-branch by use of the following theorem.
Theorem ZRS. If a 0, the following assertions are equivalent:
1. (1)
2. (2)
3. (3)
where a' is a with its rightmost k bits set to 0 (that is, a' = a & -2k).
Proof. (Assume a 32-bit machine). To see that (1) is equivalent to (2), clearly the assertion -a x a is equivalent to abs(x) a. Then, Theorem ZRU applies, because both sides of this inequality are nonnegative.
To see that (1) is equivalent to (3), note that assertion (1) is equivalent to itself with a replaced with a'. Then, by the theorem on bounds checking on page 52, this in turn is equivalent to
Because x + a' ends in k 0-bits if and only if x does, Theorem ZRU applies, giving the result.
Using part (3) of this theorem, the test that n is a multiple of d, where n and d 2 are signed integers and d = do ?2k with do odd, is
(a' may be computed at compile time, because d is a constant.)
As an example, the following code tests a signed integer n to see if it is a multiple of 100. Notice that the constant can always be derived from the constant a' by a shift of k - 1 bits, saving an instruction or a load from memory to develop the comparand.
li牋牋 M,0xC28F5C29?Load mult. inverse of 25.
mul牋?q,M,n牋牋牋牋 q = right half of M*n.
li牋牋 c,0x051EB850?c = floor((2**31 - 1)/25) & -4.
add牋?q,q,c牋牋牋牋 Add c.
shrri?q,q,2牋牋牋牋 Rotate right two positions.
shri牋 c,c,1牋牋牋牋 Compute const. for comparison.
cmpleu t,q,c牋牋牋牋 Compare q and c, and
bt牋牋 t,is_mult牋牋 branch if n is a mult. of 100.
I think that I shall never envision
An op unlovely as division.
An op whose answer must be guessed
And then, through multiply, assessed;
An op for which we dearly pay,
In cycles wasted every day.
Division code is often hairy;
Long division's downright scary.
The proofs can overtax your brain,
The ceiling and floor may drive you insane.
Good code to divide takes a Knuthian hero,
But even God can't divide by zero!