Skip to main content

Subsection 6.2.3 Models of floating point computation

When computing with floating point numbers on a target computer, we will assume that all (floating point) arithmetic that is performed is in terms of additions, subtractions, multiplications, and divisions: \(\left\{ +, -, \times, / \right\}\text{.}\)

Subsubsection 6.2.3.1 Notation

In our discussions, we will distinguish between exact and computed quantities. The function \(\fl{ {\rm expression} }\) returns the result of the evaluation of \({\rm expression} \text{,}\) where every operation is executed in floating point arithmetic. For example, given \(\chi, \psi, \zeta, \omega \in F \) and assuming that the expressions are evaluated from left to right and order of operations is obeyed,

\begin{equation*} \fl{ \chi + \psi + \zeta/\omega } \end{equation*}

is equivalent to

\begin{equation*} \fl{ \fl{ \chi + \psi } + \fl{ \zeta / \omega } } \text{.} \end{equation*}

Equality between the quantities \({\rm lhs} \) and \({\rm rhs} \) is denoted by \(lhs = rhs\text{.}\) Assignment of \(rhs \) to \(lhs \) is denoted by \(lhs \becomes rhs\) (\(lhs \) becomes \(rhs\)). In the context of a program, the statements \(lhs := rhs\) and \(lhs := \fl{ {\rm rhs} }\) are equivalent. Given an assignment \(\kappa := expression \text{,}\) we use the notation \(\check \kappa\) (pronounced "check kappa") to denote the quantity resulting from \(\fl{ {\rm expression} }\text{,}\) which is actually stored in the variable \(\kappa\text{.}\)

Remark 6.2.3.1.

In future discussion, we will often use the notation \([ \cdot ] \) as shorthand for \(\fl{ \cdot } \text{.}\)

Subsubsection 6.2.3.2 Standard Computational Model (SCM)

The Standard Computational Model (SCM) assumes that, for any two floating point numbers \(\chi\) and \(\psi\text{,}\) the basic arithmetic operations satisfy the equality

\begin{equation*} \fl{ \chi\ {\rm op}\ \psi } = (\chi\ {\rm op}\ \psi)( 1 + \epsilon), \vert \epsilon \vert \leq \meps, \ {\rm and\ \ op}\ \in \{+, -, *, /\}. \end{equation*}

The quantity \(\epsilon\) is a function of \(\chi, \psi\) and \({\rm op}\text{.}\) Sometimes we add a subscript \((\epsilon_+, \epsilon_*, \cdots)\) to indicate v what operation generated the \((1 + \epsilon)\) error factor. We always assume that all the input variables to an operation are floating point numbers.

Remark 6.2.3.2.

We can interpret the SCM as follows: These operations are performed exactly and it is only in storing the result that a roundoff error occurs (equal to that introduced when a real number is stored as a floating point number).

Of course, what really happens is that enough digits of the result are computed so that the net effect is as if result of the exact operation was stored.

Given \(\chi, \psi \in F \text{,}\) performing any operation \({\rm op} \in \{ +, -, *, / \} \) with \(\chi \) and \(\psi \) in floating point arithmetic, \(\fl{ \chi\ {\rm op}\ \psi } \text{,}\) is a (numerically) stable operation: Let \(\zeta = \chi\ {\rm op}\ \psi \) and \(\check \zeta = \zeta + \delta\!\zeta = \fl{ \chi\ {\rm op} \psi } \text{.}\) Then \(\vert \delta\!\zeta \vert \leq \meps \vert \zeta \vert \) and hence \(\check \zeta \) is close to \(\zeta \) (it has \(k \) correct binary digits).

Subsubsection 6.2.3.3 Alternative Computational Model (ACM)

For certain problems it is convenient to use the Alternative Computational Model (ACM) (((Unresolved xref, reference "biblio-Higham"; check spelling or use "provisional" attribute))) , which also assumes for the basic arithmetic operations that

\begin{equation*} \fl{ \chi\ {\rm op}\ \psi } = \frac{\chi\ {\rm op}\ \psi}{1 + \epsilon}, \vert \epsilon \vert \leq \meps, \ {\rm and\ \ op}\ \in \{+, -, *, /\}. \end{equation*}

As for the standard computation model, the quantity \(\epsilon\) is a function of \(\chi, \psi\) and \(\mbox{\rm op}\text{.}\) Note that the \(\epsilon\)'s produced using the standard and alternative models are generally not equal. The Taylor series expansion of \(1/(1+\epsilon) \) is given by

\begin{equation*} \frac{1}{1+\epsilon} = 1 + (- \epsilon) + O( \epsilon^2 ), \end{equation*}

which explains how the SCM and ACM are related.

The ACM is useful when analyzing algorithms that involve division. In this course, we don't analyze in detail any such algorithms. We include this discussion of ACM for completeness.

Remark 6.2.3.3.

Sometimes it is more convenient to use the SCM and sometimes the ACM. Trial and error, and eventually experience, will determine which one to use.