10-16 Test for Zero Remainder after Division by a Constant

The multiplicative inverse of a divisor d can be used to test for a zero remainder after division by d [GM].

Unsigned

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,

graphics/10icon182.gif

 

That is, for graphics/10icon183.gifTherefore, for n not a multiple of d, the value of nd?/span>, reduced modulo 2W to the range 0 to 2W - 1, must exceed graphics/10icon184.gif

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 graphics/10icon185.gifand compare the rightmost W bits to graphics/10icon186.gifOn 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 graphics/icon02.gifhave the same number of trailing zeros ( graphics/icon01.gifis odd), the test that n is a multiple of d is

graphics/10icon187.gif

 

where the "mod" function is understood to reduce graphics/icon02.gifto 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 graphics/10icon188.gifdenotes the computer word a rotated right k positions (0 k 32).

graphics/10icon189.gif

 

Proof. (Assume a 32-bit machine.) Suppose graphics/10icon190.gifand x ends in k 0-bits. Then, because graphics/10icon191.gifBut graphics/10icon192.gifTherefore, graphics/10icon193.gifIf x does not end in k 0-bits, then graphics/10icon194.gifdoes not begin with k 0-bits, whereas graphics/10icon195.gifLastly, if graphics/10icon196.gifand 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 graphics/10icon197.gif

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

graphics/10icon198.gif

 

Here we used graphics/10icon199.gif

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. 

Signed, Divisor 2

For signed division, it was shown in the preceding section that if n is a multiple of d, and d is odd, then

graphics/10icon200.gif

 

Thus, for graphics/10icon201.gifwe have graphics/10icon202.gifFurthermore, 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

graphics/10icon203.gif

 

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,

graphics/10icon205.gif

 

Thus, for signed numbers, the test that n is a multiple of d, where d = do ?2k and do is odd, is

graphics/10icon206.gif

 

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) graphics/10icon207.gif

2.       (2) graphics/10icon208.gif

3.       (3) graphics/10icon209.gif

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

graphics/10icon210.gif

 

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

graphics/10icon211.gif

 

(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 graphics/10icon212.gifcan 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!