Mathematics 171 – Numerical Analysis I Discussion 1 – Computer Arithmetic September 3, 1998

Background

Last time we saw the basic idea behind decimal and binary floating point number systems, in which numbers are stored in a data structure consisting of

a) a sign,

b) a fractional part or “mantissa”, and

c) an exponent. Today, we will consider the way sums, differences, products and quotients are actually computed in floating-point number systems, and identify some situations where numerical errors can be especially severe.

In our examples today, we will ignore the decimal-to-binary conversion step, and work with decimal floating point numbers of the form

±.d_{1}d_{2}d_{3} … d_{n} × 10^{e}

in which some number n decimal digits (0 ≤ d_{i} ≤ 9) of each number are stored, and the exponents e lie in some fixed range, say −A ≤ e ≤ A. We will say that a floating point number is normalized if the leading decimal digit in the mantissa (d_{1}) is non-zero. We can “normalize” a non-zero number by adjusting the exponent (“moving the decimal point”)

– for example, writing .0023 × 10^{3} as .2300 × 10^{1}.

What happens computing in sums or differences is this (essentially, i.e. this is a slightly “fictionalized” account that preserves most of the relevant behavior!):

a) The two numbers are “aligned” (again by adjusting the exponents) so that the decimal points and exponents agree (for example by leaving the larger one in absolute value unchanged, and adjusting the smaller one).

b) The sum or difference is computed, using all the digits present, (Note: the arithmetic hardware can hold more than the n digits which are retained when numbers are stored in memory).

c) The result is put in the standard form for the floating point system, by either chopping off any digits past the nth digit in the mantissa, or by rounding to n digits.

Products and quotients are handled the same way, except that alignment is not necessary – we just multiply (or divide) the mantissas and add (or subtract) the exponents.

For the purposes of illustration, we will use a decimal floating point system with n = 4-digit mantissas, and exponents −10 ≤ e ≤ 10. Here are a couple of sample calculations:

1) .2345 × 10^{3} + .4283 × 10^{1}.

a) after alignment: = .2345 × 10^{3} + .004283 × 10^{3}.

b) sum computed using all digits: = .238783 × 10^{3} c1) result chopped to 4 digits: = .2387 × 10^{3}. c2) result rounded to 4 digits: = .2388 × 10^{3}.

2) .2345 × 10^{3} · .4283 × 10^{1}.

a) (no alignment is needed)

b) multiplying mantissas and adding exponents: = .10043635 × 10^{4} c1-c2) chopping or rounding to 4 digits gives same result: .1004 × 10^{4}.

Depending on the computer system and the software used, it may be the case that if a calculation involves several arithmetic steps, a, b, and c are performed for each intermediate step. In particular the rounding or chopping may occur after every operation.

Discussion Questions

Here are some problems for you to practice on (in each case use the 4-digit decimal floating point system used above, and find the results, first chopping, then rounding after each operation). As always, evaluate subexpressions inside parentheses first:

A) .5738 × 10^{5} − .9385 × 10^{4} B) .4076 × 10^{−2} ÷ .9292 × 10^{−3} C) (.1361×10^{2} +.5090×10^{7})·.2002×10^{4}. (The technical name for this is “overflow.” On

a real computer, this situation would cause a program crash and an error message.) D) (.1327 × 10^{0} · .2102 × 10^{0}) − .2781 × 10^{−1} E) What happened in D here is probably the single worst case for floating point arithmetic

– subtracting two nearly equal numbers. Of the four digits in the normalized result, how many are actually significant (i.e. produced by the calculation)?

To measure how big the error here is, we can use either the absolute error:

exact value − computed value

or what is usually more informative, the relative error

(exact value − computed value)/(exact value)

The relative error is, so to speak, the absolute error expressed as a fraction of the exact value.

F) Find the absolute and relative errors in the floating point computation from D. (Does it make sense to do the computation of the error in the floating point system, or should you use more decimal digits?)

G) What is the largest possible relative error you could get in this floating point number

system by subtracting two numbers? H) How many different numbers can be represented in a floating point system with n

decimal digit mantissas, and exponents −A ≤ e ≤ A if only normalized numbers (and zero) are considered? How many are there in each interval [10^{k}, 10^{k+1})? Floating point numbers are often said to be distributed logarithmically. What does this mean?

I) What happens if we try to normalize the number .00 … 01 × 10^{−A}? (The technical name for this is “underflow”; some real-world computer systems would treat the result as zero, while others would generate an error.)

J) It is clear that rounding arithmetic will usually produce numerical results superior to chopping arithmetic. Yet, chopping is actually done in many real-world computer systems! Why do you suppose that this is true?

Assignment 1

Each group should prepare one set of answers to all of the questions from this discussion.

Due: Thursday, September 10.