TAOCP 4.2.1 Exercise 12
Let u=(e_u,f_u), \qquad v=(e_v,f_v) be normalized floating point numbers in radix $b$, with $p$-digit fractions.
Section 4.2.1: Single-Precision Calculations
Exercise 12. [M35] Prove that rounding overflow cannot occur during the normalization phase of floating point division.
Verified: no
Solve time: 6m17s
Let
$$ u=(e_u,f_u), \qquad v=(e_v,f_v) $$
be normalized floating point numbers in radix $b$, with $p$-digit fractions. Thus
$$ \frac1b \le |f_u| < 1, \qquad \frac1b \le |f_v| < 1. $$
In floating point division, before normalization the quotient fraction is
$$ F=\frac{f_u}{f_v}, $$
and therefore
$$ \frac1b \le |F| < b. $$
Hence the normalization algorithm can require at most one right shift. There are two cases.
Case 1: $\frac1b \le |F| < 1$
The quotient fraction is already normalized. Let
$$ f=|F|. $$
Since $f_u$ and $f_v$ are $p$-digit fractions,
$$ f_u \le 1-b^{-p}, \qquad f_v \ge b^{-1}. $$
Therefore
$$ f =\frac{|f_u|}{|f_v|} \le \frac{1-b^{-p}}{b^{-1}} = b-b^{,1-p}. $$
But in the present case $f<1$, so the stronger bound is simply
$$ f\le 1-b^{-p}. $$
Indeed, the largest normalized $p$-digit fraction is $1-b^{-p}$, and $f_u$ cannot exceed this value.
The distance from $f$ to $1$ is therefore at least
$$ 1-f \ge b^{-p}. $$
A rounding overflow would require $f$ to lie within one half unit in the last place of $1$, namely within
$$ \frac12 b^{-p} $$
of $1$. Since
$$ b^{-p}>\frac12 b^{-p}, $$
this is impossible. Hence rounding cannot produce $1$.
Case 2: $1 \le |F| < b$
Normalization performs one right shift, giving
$$ f=\frac{|F|}{b} =\frac{|f_u|}{b,|f_v|}. $$
Using again
$$ |f_u|\le 1-b^{-p}, \qquad |f_v|\ge b^{-1}, $$
we obtain
$$ f = \frac{|f_u|}{b,|f_v|} \le \frac{1-b^{-p}}{b\cdot b^{-1}} = 1-b^{-p}. $$
Thus the normalized fraction satisfies
$$ f\le 1-b^{-p}. $$
Exactly as in Case 1, the distance from $f$ to $1$ is at least $b^{-p}$, which is larger than one half unit in the last place. Therefore rounding cannot change $f$ to $1$.
Conclusion
In every possible division,
$$ f \le 1-b^{-p} $$
after the normalization shifts have been completed. Consequently the normalized quotient is at least one full unit in the last place below $1$. It is therefore impossible for rounding to produce the value $1$, which is the event that would cause rounding overflow and require an additional normalization shift.
Hence rounding overflow cannot occur during the normalization phase of floating point division.
$$ \boxed{\text{Rounding overflow cannot occur in floating point division.}} $$