TAOCP 4.2.4 Exercise 13
Let $X$ and $Y$ denote the fraction parts of the two normalized floating point operands.
Section 4.2.4: Distribution of Floating Point Numbers
Exercise 13. ▶ [M20] The floating point multiplication routine, Algorithm 4.2.1M, requires zero or one left shifts during normalization, depending on whether $f_u f_v \ge 1/b$ or not. Assuming that the input operands are independently distributed according to the logarithmic law, what is the probability that no left shift is needed for normalization of the result?
Verified: yes
Solve time: 2m
Solution
Let $X$ and $Y$ denote the fraction parts of the two normalized floating point operands. Under the logarithmic law, each has density
$$ l(x)=\frac{1}{x\ln b}, \qquad \frac{1}{b}\le x \le 1, $$
and $X$ and $Y$ are independent.
Define the change of variables
$$ x=b^{-u}, \qquad y=b^{-v}, $$
where $0 \le u \le 1$ and $0 \le v \le 1$. This parametrization is bijective on $\left[\frac{1}{b},1\right]$. Differentiation gives
$$ dx = -(\ln b),b^{-u},du, \qquad dy = -(\ln b),b^{-v},dv. $$
The joint density transforms as
$$ l(x),dx = \frac{1}{x\ln b}\cdot (-(\ln b)x,du)= -du, $$
so the induced density of $U=-\log_b X$ is constant on $[0,1]$. Hence $U$ is uniformly distributed on $[0,1]$. The same argument gives $V=-\log_b Y$ uniformly distributed on $[0,1]$, with independence preserved.
Thus $U$ and $V$ are independent and uniformly distributed on $[0,1]$, and
$$ X = b^{-U}, \qquad Y = b^{-V}. $$
The multiplication normalization requires no left shift exactly when
$$ XY \ge \frac{1}{b}. $$
Substituting the representation,
$$ b^{-U} \cdot b^{-V} \ge b^{-1}, $$
which is equivalent to
$$ b^{-(U+V)} \ge b^{-1}, $$
and hence
$$ U+V \le 1. $$
Since $U$ and $V$ are independent uniform random variables on $[0,1]$, the probability that $U+V \le 1$ equals the area of the triangle in the unit square below the diagonal $u+v=1$. That area is
$$ \frac{1}{2}. $$
Therefore the probability that no left shift is needed during normalization is
$$ \boxed{\frac{1}{2}}. $$
This completes the proof. ∎