Theorem DC2. The least multiplier m is odd if p is not forced to equal W.

Proof. Assume that Equations (1a) and (1b) are satisfied with least (not forced) integer p, and m even. Then clearly m could be divided by 2 and p could be decreased by 1, and (1a) and (1b) would still be satisfied. This contradicts the assumption that p is minimal.

The magic number for a given divisor is sometimes unique (e.g., for W = 32, d = 7), but often it is not. In fact, experimentation indicates that it is usually not unique. For example, for W = 32, d = 6, there are four magic numbers:

However, there is the following uniqueness property:

Theorem DC3. For a given divisor d, there is only one multiplier m having the minimal value of p, if p is not forced to equal W.

Proof. First consider the case d > 0. The
difference between the upper and lower limits of inequality (4) is 2^{p}/dn_{c}.
We have already proved (7) that if p is
minimal, then 2^{p}/dn_{c} 2. Therefore, there can
be at most two values of m satisfying (4). Let m be the smaller of these values, given by (5); then m + 1 is the other.

Let p_{0}
be the least value of p for which m + 1 satisfies the right half of (4) (p_{0} is not forced to equal W). Then

This simplifies to

Dividing by 2 gives

Because (by Theorem D5 on page 140),

contradicting the assumption that p_{0} is minimal.

The proof for d < 0 is similar and will not be given.

The program for d
= 3, W = 32 is particularly short, because
there is no `add` or `shrsi` after the `mulhs`. What other divisors have this short program?

We consider only positive divisors. We wish
to find integers m and p that satisfy equations (1a) and (1b), and for
which p = W and
0 m 2^{W} ^{- 1}. Because any integers m and p that satisfy
equations (1a) and (1b) must also
satisfy (4), it suffices to find those divisors d
for which (4) has a solution with p = W and 0 m < 2^{W} ^{- 1}. All
solutions of (4) with p = W are given by

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

The weakest restriction on rem(2^{W}, d) is
with k = 1 and n_{c}
at its minimal value of 2^{W} ^{- 2}.
Hence we must have

that is, d
divides 2^{W} + 1, 2^{W} + 2, or 2^{W}
+ 3.

Now let us see which of these factors actually have optimal programs.

If d divides
2^{W} + 1, then rem(2^{W}, d) = d - 1. Then a solution of (6) is p = W, because the
inequality becomes

which is obviously true, because n_{c} < 2^{W}
^{- 1}. Then in the calculation of m we
have

which is less than 2^{W}
^{- 1} for d 3 (d 2 because d divides 2^{W}
+ 1). Hence all the factors of 2^{W} +
1 have optimal programs.

Similarly, if d
divides 2^{W} + 2, then rem(2^{W}, d) = d - 2. Again, a solution of (6) is p = W, because the
inequality becomes

which is obviously true. Then in the calculation of m we have

which exceeds 2^{W}
^{- 1} - 1 for d = 2, but which is less
than or equal to 2^{W} ^{- 1} -
1 for W 3, d 3 (the case W = 3 and d = 3 does
not occur, because 3 is not a factor of 2^{3} + 2 = 10). Hence all
factors of 2^{W} + 2, except for 2 and
the cofactor of 2, have optimal programs. (The cofactor of 2 is (2^{W} + 2)/2, which is not representable as a W-bit signed integer).

If d divides
2^{W} + 3, the following argument shows
that d does not have an optimal program. Because
rem(2^{W}, d) = d - 3, inequality (21) implies that we must have

for some k =
1, 2, 3, ? The weakest restriction is with k =
1, so we must have n_{c} < 2^{W}/3.

From (3a), n_{c}
2^{W} ^{- 1} - d, or d 2^{W} ^{- 1} - n_{c}. Hence it is necessary that

Also, since 2, 3, and 4 do not divide 2^{W} + 3, the smallest possible factor of 2^{W} + 3 is 5. Hence the largest possible
factor is (2^{W} + 3)/5. Thus, if d divides 2^{W}
+ 3 and d has an optimal program, it is
necessary that

Taking reciprocals of this with respect to 2^{W} + 3 shows that the cofactor of d, (2^{W} +
3)/d, has the limits

For W 5,
this implies that the only possible cofactors are 5 and 6. For W < 5, it is easily verified that there are no
factors of 2^{W} + 3. Because 6 cannot
be a factor of 2^{W} + 3, the only
possibility is 5. Therefore, the only possible factor of 2^{W} + 3 that might have an optimal program
is (2^{W} + 3)/5.

For d = (2^{W} + 3)/5,

For W 4,

so

This exceeds (2^{W}/3),
so d = (2^{W}
+ 3)/5 does not have an optimal program. Because for W
< 4 there are no factors of 2^{W} +
3, we conclude that no factors of 2^{W}
+ 3 have optimal programs.

In summary, all the factors of 2^{W} + 1 and of 2^{W}
+ 2, except for 2 and (2^{W} + 2)/2,
have optimal programs, and no other numbers do. Furthermore, the above proof
shows that algorithm magic (Figure 10-1 on
page 174) always produces the optimal program when it exists.

Let us consider the specific cases W = 16, 32, and 64. The relevant factorizations are shown below.

Hence we have the results that for W = 16, there are 20 divisors that have optimal programs. The ones less than 100 are 3, 6, 9, 11, 18, 22, 33, 66, and 99.

For W = 32, there are six such divisors: 3, 6, 641, 6,700,417, 715,827,883, and 1,431,655,766.

For W = 32, there are 126 such divisors. The ones less than 100 are 3, 6, 9, 18, 19, 27, 38, 43, 54, 57, and 86.