\magnification = \magstep1
\centerline{Mathematics 171 -- Numerical Analysis I}
\centerline{Discussion 1 -- Computer Arithmetic}
\centerline{September 3, 1998}
\bigskip
\noindent
{\bf Background}
\bigskip
Last time we saw the basic idea behind decimal and binary
{\it floating point number systems}, in which numbers are 
stored in a data structure consisting of 
\item{a)}  a sign,
\item{b)}  a fractional part or ``mantissa'', and
\item{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.  

\noindent
In our examples today, we will ignore the decimal-to-binary conversion
step, and work with {\it decimal\/} floating point numbers of
the form
$$\pm .d_1 d_2 d_3 \ldots d_n \times 10^e$$
in which some number $n$ decimal digits ($0 \le d_i \le 9$) of each number are
stored, and the exponents $e$ lie in some fixed range, say $-A \le e \le A$.
We will say that a floating point number is {\it 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 \times 10^3$ as $.2300 \times 10^1$.
 
What happens computing in sums or differences is this ({\it essentially\/}, 
i.e. this is a slightly ``fictionalized'' account that preserves
most of the relevant behavior!):
\item{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).
\item{b)}  The sum or difference is 
computed, using {\it all\/} the digits present,  (Note: the arithmetic hardware 
can hold more than the $n$ digits which are retained when numbers are
stored in memory).
\item{c)}  The result is put in the standard form for
the floating point system, by either {\it chopping\/} off any 
digits past the $n$th digit in the mantissa, or by {\it rounding\/}
to $n$ digits.
\bigskip
\noindent
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.
\bigskip
\noindent
For the purposes of illustration, we will use a decimal floating
point system with $n = 4$-digit mantissas, and exponents $-10 \le e \le 10$.
Here are a couple of sample calculations:
\bigskip
\noindent
1)  $.2345 \times 10^3 + .4283 \times 10^1$.
\smallskip
\noindent
a) after alignment: $= .2345 \times 10^3 + .004283 \times 10^3$.
\smallskip
\noindent
b) sum computed using all digits: $= .238783 \times 10^3$
\smallskip
\noindent
c1) result chopped to 4 digits: $= .2387 \times 10^3$.
\smallskip
\noindent
c2) result rounded to 4 digits: $= .2388 \times 10^3$.  
\bigskip
\noindent
2)  $.2345 \times 10^3 \cdot .4283 \times 10^1$.
\smallskip
\noindent
a) (no alignment is needed)
\smallskip
\noindent
b) multiplying mantissas and adding exponents: $ = .10043635 \times 10^4$
\smallskip
\noindent
c1-c2) chopping or rounding to 4 digits gives
same result: $.1004 \times 10^4$.
\bigskip
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 {\it each intermediate step\/}.
In particular the rounding or chopping may occur after every operation.
\bigskip
\noindent
{\bf Discussion Questions}
\bigskip
\noindent
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:
\bigskip
\item{A)}  $.5738 \times 10^5 - .9385 \times 10^4$
\item{B)}  $.4076 \times 10^{-2} \div .9292 \times 10^{-3}$
\item{C)}  $(.1361 \times 10^2 + .5090 \times 10^7)\cdot .2002 \times 10^4$.
(The technical name for this is ``overflow.''  On a real computer, this
situation would cause a program crash and an error message.)
\item{D)}  $(.1327 \times 10^0 \cdot .2102 \times 10^0) - .2781 \times 10^{-1}$
\item{E)} What happened in D here is probably the single worst case for floating
point arithmetic -- {\it subtracting two nearly equal numbers\/}.   Of the four digits in the normalized result, how many are actually 
significant (i.e. produced by the calculation)?  
\bigskip
\noindent   
To measure how big the error here is, we can use either the {\it absolute
error}:
$$ \hbox{exact value} - \hbox{computed value}$$
or what is usually more informative, the {\it relative error\/}
$$ (\hbox{exact value} - \hbox{computed value}) / (\hbox{exact value})$$
The relative error is, so to speak, the absolute error expressed as a fraction
of the exact value.  
\bigskip
\item{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 
{\it in the floating point system\/}, or should you use more decimal digits?)
\item{G)}  What is the {\it largest possible\/} relative error you could get in
this floating point number system by subtracting two numbers?
\item{H)} {\it How many\/} different numbers can be represented in a floating
point system with $n$ decimal digit mantissas, and exponents $-A \le e \le 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 {\it distributed logarithmically\/}.  What does
this mean?  
\item{I)} What happens if we try to normalize the number
$.00\ldots 01 \times 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.)
\item{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?
\bigskip
\noindent
{\bf Assignment 1}
\bigskip
Each group should prepare one set of answers to all of the questions from
this discussion.  
\bigskip
\noindent
{\bf Due:} Thursday, September 10. 
\bye 

