TAOCP 5.3.2 Exercise 15
We compute $\left\lfloor \lg(n/m) \right\rfloor$ for $n>m$ by characterizing it as the unique integer $k \ge 0$ such that $m \cdot 2^k \le n < m \cdot 2^{k+1}.$ This reformulation eliminates division...
Section 5.3.2: Minimum-Comparison Merging
Exercise 15. [12] [12] Step H1 of the binary merge algorithm may require the calculation of the expression $\lfloor \lg(n/m) \rfloor$, for $n > m$. Explain how to compute this easily without division or calculation of a logarithm.
Verified: yes
Solve time: 1m
Solution
We compute $\left\lfloor \lg(n/m) \right\rfloor$ for $n>m$ by characterizing it as the unique integer $k \ge 0$ such that
$m \cdot 2^k \le n < m \cdot 2^{k+1}.$
This reformulation eliminates division and logarithms and replaces the task by repeated doubling of $m$. Define $t_0 = m$ and construct a sequence by
$t_{k+1} = 2t_k.$
Each step preserves the identity $t_k = m \cdot 2^k$. The required quantity is the largest $k$ for which $t_k \le n$.
A direct procedure maintains a counter $k$ and a running value $t$, initialized by $t \leftarrow m$, $k \leftarrow 0$. At each stage, the comparison $2t \le n$ is performed; if it holds, the update $t \leftarrow 2t$ and $k \leftarrow k+1$ is executed. The loop terminates when $2t > n$, at which point $t = m \cdot 2^k \le n$ and $m \cdot 2^{k+1} > n$, so $k = \left\lfloor \lg(n/m) \right\rfloor$.
The test $2t \le n$ requires only a comparison after a single addition, since it is equivalent to $t+t \le n$. No division or logarithm evaluation is involved, only repeated doubling and comparison.
The value of $k$ obtained by this process is therefore the desired result.
This completes the solution. ∎