Hacker's Delight

10-10. Incorporation into a Compiler (Unsigned)

There is a difficulty in implementing an algorithm based on direct evaluation of the expressions used in this proof. Although p ≤ 2W, which is proved above, the case p = 2W can occur (e.g., for d = 2^W − 2 with W ≥ 4). When p = 2W, it is difficult to calculate m, because the dividend in (26) does not fit in a 2W-bit word.

However, it can be implemented by the “incremental division and remainder” technique of algorithm magic. The algorithm is given in Figure 10-2 for W = 32. It passes back an indicator a, which tells whether or not to generate an add instruction. (In the case of signed division, the caller recognizes this by M and d having opposite signs.)

Figure 10-2. Computing the magic number ...