Errors in computer arithmetic operations

This chapter briefly considers the machine representation of floating-point numbers and modelling of errors in computer arithmetic operations. The arithmetic performed by a computer is different from the arithmetic that we use in algebra and calculus courses. In the traditional mathematical world, numbers with an infinite number of digits are permitted. In the computational world, however, each representable number has only a finite number of digits. Input data, and also intermediate and final results of arithmetic operations, are placed in the computer memory in some standard way. To represent real numbers in some given number system, the following floating-point representation is chosen:

=±bcmb.

  (1.1)

Here, x is a real number, b is a base of the number system (usually 2, 8, or 16), c is an exponent called the characteristic, mb is a fractional part called the mantissa, and ± denotes the sign of the number x. A mantissa of a number x≠ 0 satisfies the condition:

b≤mb<1,

which makes representation (1.1) unique. One can represent any real number in the floating-point representation and this can be done in a number system with any base b> 0. However, in the case of computers, some real numbers (for instance, irrational numbers) cannot be exactly placed in a limited computer memory. All numbers which can be placed in the memory are represented there in some unique way so that all their exponents are bounded cm≤ c ≤ cp, and the mantissa is decomposed into a final b-fraction:

b=a1b+a2b2+⋯+akbk,

where an satisfy:

≤a1≤b−1,0≤an≤b−1,n=2,…,k

Example 1.1

Binary representation of a real number

Consider the real number x= 8.75. Let us represent this number in the binary form (b= 2). First, we rewrite number x as 0.546875⋅24, so c from representation (1.1) is 4 (100 in binary form). The fractional part of the number may be represented as:

=12+132+164.

Then coefficients an of the b-fraction are:

The numbers that can be stored in a given system are called machine numbers, and they form some finite subset of real numbers. The constants b, cm, cp, and k describe machine numbers in a satisfactory way, but they are not very useful in applications. It is more convenient to introduce the following set of quantities: b, ɛ0, ɛ1, and ɛ∞. These parameters, like the previous ones, depend only on a particular computer, and they are defined as follows:

0=bcm−1,ε1=b1−k,ε∞=bcp1−b−k.

These parameters have the following meanings: ɛ∞ is a maximal machine number, ɛ0 is the minimal positive one, and ɛ1 is equal to the step of machine numbers on the interval from 1 to b. Parameter ɛ1 is also called the relative error of unity, because all numbers of the form 1 + x from the interval [1, l + ɛ1] are replaced by the machine number 1 with the error not exceeding ɛ1 Therefore, in the intervals (−∞, ɛ∞), (− ɛ0, 0), (0,ɛ0), (1 − ɛ1/b, 1), (1, l + ɛ1) and (ɛ∞, ∞) there are no machine numbers at all. Along with standard precision, it is possible to use higher precision to represent numbers. This can be done by widening the number of digits in the mantissa and, possibly, by widening the range of admissible exponents of computer numbers. Thus, computer numbers with higher precision are characterized by the parameters b, cm*, cp*, and k * In Table 1.1, values of the defining parameters for PCs are presented.

Table 1.1

If x∈ [− ɛ∞, ɛ∞], then it is replaced by the machine number xm. In the course of this procedure, one or another approximation schemes are used (chopping or rounding). In terms of xm, one of two machine numbers closest to x is taken. As a result of such replacement of x by xm, the error x− xm arises. For ɛ0≤|x|≤ɛ∞ the error is estimated by the quantity ɛ1|x|, that is, |x− xm|≤ɛ1|x|. If |x|∈(0, ɛ0), then xm can take one of two values: 0 or ɛ0, and it is clear that in both cases |x− xm|≤ɛ0|x|. For this reason, parameter ɛ0 is also called the absolute error of zero. These estimates can be unified into

m=x1+α+β,|α|≤ε1,|β|≤ε0,

  (1.2)

which holds for all x∈ [ɛ∞, ɛ∞].

Arithmetic operations on computers are performed on machine numbers. In many cases, the result of these operations may not be a machine number at all. In other words, the result of an arithmetic operation (machine result), being a machine number, may not coincide with the exact result. For example, a quotient of two machine numbers a and b often requires an infinite number of b-digits for its representation. So, the machine result differs from the exact result of the operation a/b. Thus, the main property of machine arithmetic can be postulated as follows: the machine result of one of four arithmetic operations on two machine numbers can be represented as an outcome of placing the exact result of this operation into machine memory. In order to distinguish machine operations from ordinary (exact) ones, we will denote them by enclosing the appropriate symbol in angle brackets. Then, according to the above postulate, we have

+b=a+bm,a−b=a−bm,a×b=a×bm,a/b=a/bm.

  (1.3)

Formulae (1.3) state that only one of two machine numbers closest to the exact result of an operation will be taken as the machine result, but this machine result will also depend on the operation and operands (numbers a and b). In particular, if the exact result falls outside the interval of numbers which can be represented in the computer (the result x∉[− ɛ∞, ɛ∞]), we encounter an overflow, which is treated as an error. In a correctly working program such a situation should be avoided. If the exact result happens to be smaller in absolute value than ɛ0, we may have problems with underflow, and such a situation is also undesirable.

Using formulae (1.2) and (1.3) we can obtain the formulae for modelling of errors:

+b=a+bm=(a+b)(1+α)+β,a−b=a−bm=(a−b)(1+α)+β,a×b=a×bm=(ab)(1+α)+β,a/b=a/bm=(a/b)(1+α)+β.

Thus, formulae for the error estimates of floating-point operations result in a general formula

a*b−a*b|≤ε0+ε1|a*b|,

where * denotes any one of the four arithmetic operations. This estimate can be used to derive error estimates for the multiple floating-point operations. For example, if we assume that β = 0, then the error of computation of

n=1Nan

can be estimated as

1×a2×⋯×aN−∏n=1Nan≤ε1N−1∏n=1N|an|.

With...