TAOCP 4.2.2 Exercise 4
Yes.
Section 4.2.2: Accuracy of Floating Point Arithmetic
Exercise 4. [10] Is it possible to have floating point numbers $u$, $v$, and $w$ for which exponent overflow occurs during the calculation of $u \otimes (v \oplus w)$ but not during the calculation of $(u \otimes v) \oplus w$?
Verified: yes
Solve time: 7m
Solution
Yes.
Let $\Omega$ denote the largest positive floating-point number. We will construct floating-point numbers $u,v,w$ such that overflow occurs while evaluating
$$ u\otimes(v\oplus w), $$
but no overflow occurs while evaluating
$$ (u\otimes v)\oplus w. $$
Choose a floating-point number $u>1$. Let
$$ \delta=\Omega!\left(1-\frac1u\right). $$
Since the floating-point numbers are discrete, there exists a positive floating-point number $\varepsilon$ with
$$ 0<\varepsilon<\delta . $$
Now define
$$ w=\Omega-\varepsilon, \qquad v=\frac{\varepsilon}{u}. $$
By choosing $\varepsilon$ to be a sufficiently small floating-point unit near $\Omega$, we may arrange that $w$ is a floating-point number. Since $u$ and $\varepsilon$ are floating-point numbers, $v$ can likewise be chosen as a floating-point number. Thus $u,v,w$ are all floating-point numbers.
We have
$$ uv+w = \varepsilon+(\Omega-\varepsilon) = \Omega. $$
Hence the exact product $uv=\varepsilon$ is finite and does not overflow, and the exact sum $uv+w$ is exactly $\Omega$. Therefore neither operation in the evaluation of
$$ (u\otimes v)\oplus w $$
overflows. In fact,
$$ u\otimes v=\varepsilon, \qquad (u\otimes v)\oplus w=\Omega. $$
Now consider the other parenthesization. Since
$$ v+w = \frac{\varepsilon}{u}+\Omega-\varepsilon = \Omega-\varepsilon!\left(1-\frac1u\right) < \Omega, $$
the addition $v\oplus w$ does not overflow. Its value is a finite floating-point number near $v+w$.
Moreover,
$$ u(v+w) = u\Omega-\varepsilon(u-1). $$
Because $\varepsilon<\delta=\Omega(1-\frac1u)$,
$$ \varepsilon(u-1) < \Omega!\left(1-\frac1u\right)(u-1) = \frac{\Omega (u-1)^2}{u}, $$
and therefore
$$ u(v+w) = u\Omega-\varepsilon(u-1)
u\Omega-\frac{\Omega (u-1)^2}{u} = \Omega. $$
Thus the exact result of multiplying $u$ by $v+w$ exceeds $\Omega$. Consequently the multiplication in
$$ u\otimes(v\oplus w) $$
overflows.
We have therefore exhibited floating-point numbers $u,v,w$ for which overflow occurs during the evaluation of $u\otimes(v\oplus w)$, while no overflow occurs during the evaluation of $(u\otimes v)\oplus w$.
Hence the answer is yes. ∎