TAOCP 4.3.1 Exercise 37
If $d$ is a power of 2 on a binary computer, then multiplication or division by $d$ can be accomplished by simple bit shifts.
Section 4.3.1: The Classical Algorithms
Exercise 37. [**] [20] (E. Salamin.) Explain how to avoid the normalization and unnormalization steps of Algorithm D, when $d$ is a power of 2 on a binary computer, without changing the sequence of trial quotient digits computed by that algorithm. (How can $\hat{q}$ be computed in step D3 if the normalization of step D1 hasn't been done?)
Verified: no
Solve time: 4m01s
If $d$ is a power of 2 on a binary computer, then multiplication or division by $d$ can be accomplished by simple bit shifts. In Algorithm D, the normalization step D1 multiplies both the dividend and the divisor by a factor $f$ so that the leading digit of the divisor is at least half the base. When $d = 2^k$, this factor $f$ is itself a power of 2, and multiplying by $f$ corresponds exactly to shifting the binary digits left by $k$ positions. Similarly, the unnormalization step D7 corresponds to a right shift by $k$ positions. Since shifting does not alter the relative ratios of the high-order digits, the trial quotient $\hat{q}$ computed in step D3 is identical whether the divisor has been explicitly normalized or not. Therefore, one can compute $\hat{q}$ directly from the original (unnormalized) digits of the dividend and divisor by effectively incorporating the shift into the computation, avoiding any explicit multiplication or division by $f$. This preserves the exact sequence of trial quotient digits and eliminates the need for separate normalization and unnormalization operations. ∎