Lost and Preserved Properties of Arithmetic

Posted by Beetle B. on Tue 22 January 2019

Floating point addition and multiplication are still commutative.

Associativity is compromised, though. An example: Let \(a=\beta^{p+1},b=-\beta^{p+1},c=1\). Then \(\RN(a+\RN(b+c))=\RN(\beta^{p+1}-\beta^{p+1})=0\). But \(\RN(\RN(a+b)+c)=\RN(0+1)=1\).

For multiplication, the difference due to associativity is smaller. We know that if there is no overflow or underflow, then:

\begin{equation*} \RN(ab)=ab(1+\epsilon_{1}) \end{equation*}

with \(|\epsilon_{1}|\le\frac{1}{2}\beta^{1-p}\)

So \(P_{1}=\RN(\RN(ab)c)=abc(1+\epsilon_{1})(1+\epsilon_{2})\)

Likewise, \(P_{1}=\RN(a\RN(bc))=abc(1+\epsilon_{3})(1+\epsilon_{4})\).

Now:

\begin{equation*} \frac{P_{1}}{P_{2}}=\frac{(1+\epsilon_{1})(1+\epsilon_{2})}{(1+\epsilon_{3})(1+\epsilon_{4})} \end{equation*}

We know that \(-\frac{1}{2}\beta^{1-p}\le\epsilon_{i}\le\frac{1}{2}\beta^{1-p}\). And thus \(1-\frac{1}{2}\beta^{1-p}\le1+\epsilon_{i}\le1+\frac{1}{2}\beta^{1-p}\).

Now assuming that \(|\epsilon_{i}|\le1\) (fairly good assumption), we have:

\begin{equation*} \left(1-\frac{1}{2}\beta^{1-p}\right)^{2}\le(1+\epsilon_{1})(1+\epsilon_{2})\le\left(1+\frac{1}{2}\beta^{1-p}\right)^{2} \end{equation*}

Taking the min and max of the ratios, we have:

\begin{equation*} \left(\frac{1-\frac{1}{2}\beta^{1-p}}{1+\frac{1}{2}\beta^{1-p}}\right)^{2}\le\frac{P_{1}}{P_{2}}\le\left(\frac{1+\frac{1}{2}\beta^{1-p}}{1-\frac{1}{2}\beta^{1-p}}\right)^{2} \end{equation*}

This is not a loose bound.