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 2^{W}), where W is the machine's word size in bits, d?/span> is also odd. Thus, d?/span>
is relatively prime to 2^{W}, and as
shown in the proof of theorem MI in the preceding section, as n ranges over all 2^{W}
distinct values modulo 2^{W}, nd?/span> takes on all 2^{W}
distinct values modulo 2^{W}.

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 2^{W} to the range 0 to
2^{W} - 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 = d_{o} ?2^{k}, where d_{o}
is odd and k 1. Then, because an
integer is divisible by d if and only if it is
divisible by d_{o} and by 2^{k}, 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, 2^{W} - 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 = d_{o} ?2_{k}
with d_{o} 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 2^{W}, as n
ranges over all 2^{W} distinct values
modulo 2^{W}, nd?/span>
takes on all 2^{W} distinct values
modulo 2^{W}. Therefore, n is a multiple of d
if and only if

where the "mod" function is
understood to reduce nd?/span> to the interval [-2^{W} ^{- 1}, 2^{W} ^{- 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 2^{W}
^{- 1}. Therefore,

Thus, for signed numbers, the test that n is a multiple of d,
where d = d_{o}
?2k and d_{o}
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 & -2^{k}).

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 = d_{o} ?2^{k}
with d_{o} 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!