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
with 0 m < 2W + 1 and p W.
In the unsigned case, the magic number M is given by
Because (22) must hold for
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 Then
These imply that nc 2W - 1.
Because (22) must hold for n = nc,
Combining this with (23) gives
Because m is to be the least integer satisfying (25), it is the next integer greater than or equal to 2p/d梩hat is,
Combining this with the right half of (25) and simplifying gives
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).
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,
Because nc, d 2W - 1, this becomes
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.
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.