10-9 Unsigned Division by Divisors 1

Given a word size W 1 and a divisor d, 1 d < 2W, we wish to find the least integer m and integer p such that

Equation 22



with 0 m < 2W + 1 and p W.

In the unsigned case, the magic number M is given by



Because (22) must hold for graphics/10icon133.gif

Equation 23



As in the signed case, let nc be the largest value of n such that rem(nc, d) = d - 1. It can be calculated from graphics/10icon135.gifThen

Equation 24a




Equation 24b



These imply that nc 2W - 1.

Because (22) must hold for n = nc,






Combining this with (23) gives

Equation 25



Because m is to be the least integer satisfying (25), it is the next integer greater than or equal to 2p/d梩hat is,

Equation 26



Combining this with the right half of (25) and simplifying gives

Equation 27



The Algorithm (Unsigned)

Thus, the algorithm is to find by trial and error the least p W satisfying (27). Then m is calculated from (26). This is the smallest possible value of m satisfying (22) with p W. As in the signed case, if (27) is true for some value of p, then it is true for all larger values of p. The proof is essentially the same as that of Theorem DC1, except Theorem D5(b) is used instead of Theorem D5(a).

Proof That the Algorithm Is Feasible (Unsigned)

We must show that (27) always has a solution and that 0 m < 2W + 1.

Because for any nonnegative integer x there is a power of 2 greater than x and less than or equal to 2x + 1, from (27),



Because 0 rem(2p - 1, d) d - 1,

Equation 28



Because nc, d 2W - 1, this becomes




Equation 29



Thus, (27) always has a solution.

If p is not forced to equal W, then from (25) and (28),



If p is forced to equal W, then from (25),



Because 1 d 2W - 1 and nc 2W - 1,



Hence in either case m is within limits for the code schema illustrated by the "unsigned divide by 7" example.

Proof That the Product Is Correct (Unsigned)

We must show that if p and m are calculated from (27) and (26), then (22) is satisfied.

Equation (26) and inequality (27) are easily seen to imply (25). Inequality (25) is nearly the same as (4), and the remainder of the proof is nearly identical to that for signed division with n 0.