TAOCP 4.2.4 Exercise 1
Write the normalized decimal floating point numbers in Knuth's form u=f_u10^{e_u},\qquad v=f_v10^{e_v}, where
Section 4.2.4: Distribution of Floating Point Numbers
Exercise 1. [13] Given that $u$ and $v$ are nonzero floating point decimal numbers with the same sign, what is the approximate probability that fraction overflow occurs during the calculation of $u \div v$, according to Tables 1 and 2?
Verified: yes
Solve time: 7m34s
Solution
Write the normalized decimal floating point numbers in Knuth's form
$$ u=f_u10^{e_u},\qquad v=f_v10^{e_v}, $$
where
$$ 0.1\le f_u,f_v<1. $$
Then
$$ \frac uv=\frac{f_u}{f_v},10^{e_u-e_v}. $$
Since
$$ 0.1\le f_u,f_v<1, $$
the quotient of the fractions satisfies
$$ 0.1<\frac{f_u}{f_v}<10. $$
Therefore at most one normalization shift can be required.
Fraction overflow occurs precisely when the fractional part of the quotient is at least $1$, that is,
$$ \frac{f_u}{f_v}\ge 1, $$
or equivalently,
$$ f_u\ge f_v. $$
Thus the desired probability is
$$ P(f_u\ge f_v). $$
The statistical model underlying Tables 1 and 2 treats the normalized fractions of floating point numbers as independent samples from the same distribution. Hence $f_u$ and $f_v$ are identically distributed. By symmetry,
$$ P(f_u>f_v)=P(f_v>f_u). $$
Since the probability that two independently chosen fractions are exactly equal is negligible,
$$ P(f_u\ge f_v)\approx \frac12 . $$
Therefore the approximate probability that fraction overflow occurs during the computation of $u\div v$ is
$$ \boxed{\frac12 \approx 0.50}. $$
So about half of all divisions of same-sign normalized decimal floating point numbers require the quotient fraction to be shifted right one decimal place during normalization.