TAOCP 1.2.2 Exercise 24
The method based on Eqs.
Section 1.2.2: Numbers, Powers, and Logarithms
Exercise 24. [15] Explain how the method used for calculating logarithms to the base 10 at the end of this section can be modified to produce logarithms to base 2.
Verified: yes
Solve time: 37s
Solution
The method based on Eqs. (17)–(19) computes $\log_{10} x$ by repeatedly squaring and comparing with the base $10$. To compute logarithms to base $2$, we replace every occurrence of $10$ by $2$.
We seek a binary expansion
$$ \log_2 x = n + b_1/2 + b_2/4 + b_3/8 + \cdots, $$
where each $b_k$ is either $0$ or $1$.
First determine the integer $n$ such that
$$ 1 \le x/2^n < 2. $$
Set
$$ x_0 = x/2^n. $$
Then define, for $k \ge 1$,
$$ \begin{aligned} b_k &= 0, & x_k &= x_{k-1}^2, \qquad \quad \text{if} \quad x_{k-1}^2 < 2; \ b_k &= 1, & x_k &= x_{k-1}^2/2, \quad \text{if} \quad x_{k-1}^2 \ge 2. \end{aligned} $$
The analogue of Eq. (19) is
$$ 1 \le x_k = x^{2^k} \big/ 2^{,2^k(n+b_1/2+\cdots+b_k/2^k)} < 2. $$
This is proved by induction on $k$.
For $k=0$,
$$ x_0=x/2^n, $$
and the choice of $n$ gives
$$ 1 \le x_0 < 2. $$
Assume the inequality holds for $x_{k-1}$. Then
$$ 1 \le x_{k-1} < 2, $$
hence
$$ 1 \le x_{k-1}^2 < 4. $$
If $x_{k-1}^2<2$, we set $b_k=0$ and $x_k=x_{k-1}^2$, so
$$ 1 \le x_k < 2. $$
If $x_{k-1}^2\ge2$, we set $b_k=1$ and $x_k=x_{k-1}^2/2$, so again
$$ 1 \le x_k < 2. $$
In either case,
$$ x_k = x_{k-1}^2/2^{b_k}. $$
Substituting the induction hypothesis,
$$ x_k = \left( x^{2^{k-1}} \big/ 2^{,2^{k-1}(n+b_1/2+\cdots+b_{k-1}/2^{k-1})} \right)^2 \big/ 2^{b_k}. $$
Therefore
$$ x_k = x^{2^k} \big/ 2^{,2^k(n+b_1/2+\cdots+b_k/2^k)}, $$
which establishes the formula for all $k$.
Since every $x_k$ remains in the interval $[1 \ldotp\ldotp 2)$, the quantity
$$ n+b_1/2+\cdots+b_k/2^k $$
approaches $\log_2 x$ as $k \to \infty$. Thus the method computes binary logarithms directly. This completes the proof.
∎