### 10-9 Unsigned
Division by Divisors 1

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

**Equation 22**

with 0 m < 2^{W}
^{+ 1} and p W.

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

Because (22) must hold for

**Equation 23**

As in the signed case, let n_{c} be the largest value of n such that rem(n_{c},
d) = d - 1. It
can be calculated from Then

**Equation 24a**

and

**Equation 24b**

These imply that n_{c}
2^{W} ^{- 1}.

Because (22) must hold for n = n_{c},

or

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 2^{p}/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 < 2^{W} ^{+ 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(2^{p} ^{- 1}, d) d - 1,

**Equation 28**

Because n_{c},
d 2^{W} ^{- 1}, this becomes

or

**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 2^{W} - 1 and n_{c}
2^{W} ^{- 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.