TAOCP 4.3.1 Exercise 24

Section 4.3.1: The Classical Algorithms

Exercise 24. [M20] Using the law of the distribution of leading digits explained in Section 4.2.4, give an approximate formula for the probability that $d = 1$ in Algorithm D. (When $d = 1$, we can omit most of the calculation in steps D1 and D8.)

Verified: yes
Solve time: 3m02s

Solution

Section 4.2.4 gives the law of distribution of leading digits in radix $b$ representation. For a “random” large integer uniformly distributed over many magnitudes, the probability that its leading digit is $k$ is approximately

$$ \Pr(\text{leading digit } = k) \approx \log_b!\left(1 + \frac{1}{k}\right). $$

In Algorithm D, the quantity $d$ denotes the leading digit of the divisor after normalization, so the event $d = 1$ corresponds exactly to the divisor having leading digit $1$ in radix $b$.

Substituting $k = 1$ into the leading-digit law gives

$$ \Pr(d = 1) \approx \log_b(2). $$

Equivalently, in natural logarithms,

$$ \Pr(d = 1) \approx \frac{\ln 2}{\ln b}. $$

In the common case $b = 10$, this becomes

$$ \Pr(d = 1) \approx \log_{10}(2) \approx 0.3010. $$

Thus the approximate probability that $d = 1$ in Algorithm D is

$$ \boxed{\Pr(d = 1) \approx \log_b(2)}. $$