[SOLVED] CS PA 19104-2688.

Numerical Computing
with IEEE Floating Point Arithmetic
Copyright 2001 Society for Industrial and Applied Mathematics

Copyright By Assignmentchef assignmentchef

with IEEE Floating
Point Arithmetic
Including One Theorem, One Rule of Thumb, and One Hundred and One Exercises
. Institute of Mathematical Sciences University,
Society for Industrial and Applied Mathematics Philadelphia
Copyright 2001 Society for Industrial and Applied Mathematics

Copyright 2001 by the Society for Industrial and Applied Mathematics. 10 9 8 7 6 5 4 3 2 1
All rights reserved. Printed in the United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688.
Library of Congress Cataloging-in-Publication Data
Overton,.
Numerical computing with IEEE floating point arithmetic /. Overton.
Includes bibliographical references and index. ISBN 0-89871-482-6
I. Computer arithmetic. 2. Floating-point arithmetic. 3. Numerical calculations. I. Title.
QA76.9.M35 O94 2001 004.0151dc21
is a registered trademark.
Copyright 2001 Society for Industrial and Applied Mathematics

Dedicated to girls who like math especially my daughter Sa
Copyright 2001 Society for Industrial and Applied Mathematics

Preface ix Acknowledgments xi
1 Introduction 1
2 The Real Numbers 5
3 Computer Representation of Numbers 9
4 IEEE Floating Point Representation 17
5 Rounding 25
6 Correctly Rounded Floating Point Operations 31
7 Exceptions 41
8 The Intel Microprocessors 49
9 Programming Languages 55
10 Floating Point in C 59
11 Cancellation 71
12 Conditioning of Problems 77
13 Stability of Algorithms 83
14 Conclusion Bibliography Index
97 101 105
Copyright 2001 Society for Industrial and Applied Mathematics

Numerical computing is a vital part of the modern scientific infrastructure. Almost all numerical computing uses floating point arithmetic, and almost every modern computer implements the IEEE1 binary floating point standard, published in 1985. This standard is arguably the most important in the computer industry, the result of an unprecedented cooperation between academic computer scientists and the cutting edge of industry. Nonetheless, many years after its publication, the key ideas of the IEEE standard remain poorly understood by many students and computer professionals. Perhaps this is because an easily accessible yet reasonably detailed discussion of the standard has not been availablehence, the evolution of this short book. Although it is intended primarily for computer science or mathematics students, as a supplement to a more traditional textbook for a course in scientific computing, numerical analysis, or computer architecture, it also aims to reach a broader audience. As well as the IEEE standard, topics include the floating point architecture of the Intel microprocessors, a discussion of programming language support for the standard, and an introduction to the key concepts of cancellation, conditioning, and stability. The book should be accessible to any reader with an interest in computers and mathematics. Some basic knowledge of calculus and programming is assumed in the second half. The style is not that of a traditional textbook. There is enough variety of content that all but the most expert readers will find something of interest here.
A web page for the book is maintained at http://www.cs.nyu.edu/cs/faculty/overton/book/
Refer to this page for corrections to the text, to download programs from the book, and to link to the web pages mentioned in the bibliography, which will be updated as necessary.
1Institute for Electrical and Electronics Engineers. IEEE is pronounced I triple E. ix
Copyright 2001 Society for Industrial and Applied Mathematics

Acknowledgments
Special thanks go to for introducing me to the IEEE floating point standard years ago, answering many questions, and encouraging me to complete this work. Thanks also to, without whom we would not have the standard, and to, who taught from an early version of this book and made many helpful suggestions. I am also grateful to many other people for their detailed comments, particularly,,,,, and. Being part of a network of colleagues like these is the greatest pleasure of my professional life. I particularly thank and for their crucial support during my early postdoctoral research career; I would not have been able to begin this work without them. Thanks also to,, and for pointing out errors in the first printing that are corrected in this second printing.
Many thanks to for her enthusiasm for publishing this book despite its unconventional format, to for her careful copy editing, and to all those involved in the production process. The publication of this book is one of many rewarding aspects of my association with SIAM during the past decade.
On a more personal note, I honor the memory of my father, David, who continues to inspire me many years after his passing, and I especially thank three wonderful people: my mother Kathie, my daughter Eleuthera, and my best friend Renan.
Copyright 2001 Society for Industrial and Applied Mathematics

Accurate reckoning: The entrance into knowledge of all existing things and all obscure secrets
AHMOSE`, The Rhind Mathematical Papyrus, c. 1650 B.C.
I am a HAL Nine Thousand computer Production Number 3. I became operational at the in Urbana, Illinois, on January 12, 1997. The quick brown fox jumps over the lazy dog. The rain in Spain is mainly in the plain. Daveare you still there? Did you know that the square root of 10 is 3.162277660168379?
Log 10 to the base e is 0.434294481903252 . . . correction, that is log e to the base 10 . . . The reciprocal of 3 is 0.333333333333333333333 . . . 2 times 2 is . . . 2 times 2 is . . . approximately 4.101010101010101010 . . . I seem to be having difficulty . . .
HAL, in 2001: A Space Odyssey
Copyright 2001 Society for Industrial and Applied Mathematics

Introduction
Numerical computing means computing with numbers, and the subject is almost as old as civilization itself. Ancient peoples knew techniques to carry out many numerical tasks. Among the oldest computational records that we have is the Egyptian Rhind Papyrus from about 1650 B.C. [Cha79], quoted on the previous page. Counting stones and counting rods have been used for calculation for thousands of years; the abacus originated as a flat surface with counting stones and was used extensively in the ancient world long before it evolved into the device with beads on wires that was common in Asia until recently. The abacus was the basis of calculation in Europe until the introduction of our familiar positional decimal notation from the Middle East, beginning in the 13th century. By the end of the 16th century, positional decimal notation was in standard use throughout Europe, as it became widely recognized for its computational convenience.
The next key development was the invention and tabulation of logarithms by at the beginning of the 17th century; his idea was that time-consuming multi- plication and especially division may be avoided by adding or subtracting logarithms, using tabulated values. laid the foundations of modern numerical com- puting later in the 17th century, developing numerical techniques for the solution of many mathematical problems and inventing calculus along the way. Several of New- tons computational methods still bear his name. In Newtons footsteps followed Euler, Lagrange, Gauss, and many other great mathematicians of the 18th and 19th centuries.
The idea of using physical devices as an aid to calculation is an old one. The abacus has already been mentioned. The slide rule was invented soon after Napiers discovery of logarithms, although it was not commonly used until the middle of the 19th cen- tury. Numbers are represented on a slide rule explicitly in a logarithmic scale, and its moving rule and cursor allow multiplication and division to be carried out easily, accu- rate to about three decimal digits. This simple, inexpensive device was used by many generations of engineers and remained in common use until about 1975, when it was made obsolete by cheap electronic calculators. Mechanical calculating machines were devised by Schickard, Pascal, and Leibnitz in the 17th century; their descendants also remained in use until about 1975. The idea of a programmable machine that would operate without human intervention was developed in great depth by in the 19th century, but his ideas were way ahead of his time and were mostly ignored. During World War II, scientific laboratories had rooms full of people doing different parts of a complicated calculation using pencil and paper, slide rules, and mechanical calculators. At that time, the word computer referred to a person, and those group calculations may be viewed as the early steps of parallel computing.
Copyright 2001 Society for Industrial and Applied Mathematics

2 NUMERICAL COMPUTING WITH IEEE ARITHMETIC The Computer Age
The machine often described as the worlds first operating computer was the Z3, built by the engineer in Germany in 19391941. The Z3 used electromechanical switching devices and computed with binary floating point numbers, a concept to be described in detail in subsequent chapters.2 Although Zuse developed his machines during World War II, his government took no interest in his work. Slightly later, and in great secrecy, the British government developed a powerful electronic code-breaking machine, the Colossus. The first general-purpose operational electronic computer3 is usually said to be the ENIAC (Electronic Numerical Integrator And Computer), a decimal machine with 18,000 vacuum tubes that was built by Eckert and Mauchly at the University of Pennsylvania in 19431945. Eckert was the electronics expert and Mauchly had the experience with extensive numerical computations. The intellectual giants who most influenced the postwar computer design in England and the United States were, one of the architects of the Colossus project, and John von Neumann, the Hungarian mathematician at Princeton. Two ideas in particular were advocated by von Neumann: the storage of instructions in the memory of the computer and the use of binary rather than decimal storage and arithmetic. The first fully functional stored-program electronic computers were built in England in 19481949; besides Turing, key leaders there included and. In the late 1940s and early 1950s, it was feared that the rounding errors inherent in floating point computing would make nontrivial calculations too inaccurate to be useful. Wilkinson demonstrated conclusively that this was not the case with his extensive computational experiments and innovative analysis of rounding errors accumulated in the course of a computation. Wilkinsons analysis was inspired by the work of Goldstine and von Neumann and of Turing [Wil64]. For more on the early history of computers, see [Wil85]. For a remarkable collection of essays by a cast of stars from the early days of computing, see [MHR80].
During the 1950s, the primary use of computers was for numerical computing in scientific applications. In the 1960s, computers became widely used by large busi- nesses, but their purpose was not primarily numerical; instead, the principal use of computers became the processing of large quantities of information. Nonnumerical information, such as character strings, was represented in the computer using binary numbers, but the primary business applications were not numerical in nature. During the next three decades, computers became ever more widespread, becoming available to medium-sized businesses in the 1970s and to many millions of small businesses and individuals during the personal computer revolution of the 1980s and 1990s. The vast majority of these computer users do not see computing with numbers as their primary interest; instead, they are interested in the processing of information, such as text, images, and sound. Users are often not aware that manipulation of images and sound involves a lot of numerical computing.
Science Today
In scientific disciplines, numerical computing is essential. Physicists use computers to solve complicated equations modeling everything from the expansion of the universe to the microstructure of the atom, and to test their theories against experimental
2Ideas that seem to originate with Zuse include the hidden significand bit [Knu98, p. 227], to be discussed in Chapter 3, the use of and NaN [Kah96b], to be discussed in Chapter 7, the main ideas of algorithmic programming languages [Wil85, p. 225], and perhaps the concept of a stored program [Zus93, p. 44]. His autobiography [Zus93] gives an amazing account of his successful efforts at computer design and construction amid the chaos of World War II.
3A much more limited machine was developed a little earlier in Iowa.
Copyright 2001 Society for Industrial and Applied Mathematics

CHAPTER 1. INTRODUCTION 3
data. Chemists and biologists use computers to determine the molecular structure of proteins. Medical researchers use computers for imaging techniques and for the statistical analysis of experimental and clinical observations. Atmospheric scientists use numerical computing to process huge quantities of data and to solve equations to predict the weather. Electronics engineers design ever faster, smaller, and more reliable computers using numerical simulation of electronic circuits. Modern airplane and spacecraft design depends heavily on computer modeling. Ironically, the tragic Challenger accident in January 1986 was due more to political errors than to scientific ones. From a scientific point of view, reentry of the space shuttle into the atmosphere was a far more delicate and difficult procedure than lift-off, and many nervous scientists were elated and relieved to see that their calculations had worked so well when the space shuttle first reentered the atmosphere and landed.
In brief, all fields of science and engineering rely heavily on numerical comput- ing. The traditional two branches of science are theoretical science and experimental science. Computational science is now often mentioned as a third branch, having a status that is essentially equal to, perhaps even eclipsing, that of its two older sib- lings. The availability of greatly improved computational techniques and immensely faster computers allows the routine solution of complicated problems that would have seemed impossible just a generation ago.
Copyright 2001 Society for Industrial and Applied Mathematics

The Real Numbers
The real numbers can be represented conveniently by a line. Every point on the line corresponds to a real number, but only a few are marked in Figure 2.1. The line stretches infinitely far in both directions, towards and , which are not themselves numbers in the conventional sense but are included among the extended real numbers. The integers are the numbers 0, 1, 1, 2, 2, 3, 3, . . . . We say that there is an infinite but countable number of integers; by this we mean that every integer would eventually appear in the list if we count for long enough, even though we can never count all of them. The rational numbers are those that consist of a ratio of two integers, e.g., 1/2, 2/3, 6/3; some of these, e.g., 6/3, are integers. To see that the number of rational numbers is countable, imagine them listed in an infinite two-dimensional array as in Figure 2.2. Listing the first line and then the second, and so on, does not work, since the first line never terminates. Instead, we generate a list of all rational numbers diagonal by diagonal: first 0, then 1/1; then 2/1,1/2; then 3/1,2/2,1/3; then 4/1, 3/2, 2/3, 1/4; etc. In this way, every rational number (including every integer) is eventually generated. In fact, every rational number is generated many times (e.g., 1/2 and 2/4 are the same number). However, every rational number does have a unique representation in lowest terms, achieved by canceling any common factor in the numerator and denominator (thus 2/4 reduces to 1/2).
The irrational numbers are the real numbers that are not rational. Familiar exam-
ples of irrational numbers are 2, , and e. The numbers 2 and have been studied for more than two thousand years. The number e, mentioned in the quote from HAL
on page xiii, is the limit of
as n . Investigations leading to the definition of e began in the 17th century. Every irrational number can be defined as the limit of a sequence of rational numbers,
1/2 1/2 E
4 3 2 1 0 1 2 3 4
Figure 2.1: The Real Line
Copyright 2001 Society for Industrial and Applied Mathematics

6 NUMERICAL COMPUTING WITH IEEE ARITHMETIC
1 1/1 1/2 1/3 1/4 2 2/1 2/2 2/3 2/4 3 3/1 3/2 3/3 3/4 4 4/1 4/2 4/3 4/4

Figure 2.2: The Nonzero Rational Numbers
but there is no way of listing all the irrational numbersthe set of irrational numbers
is said to be uncountable. Positional Number Systems
The idea of representing numbers using powers of 10 was used by many ancient peoples, e.g., the Hebrews, the Greeks, the Romans, and the Chinese, but the positional system we use today was not. The Romans used a system where each power of 10 required a different symbol: X for 10, C for 100 = 102, M for 1000 = 103, etc., and repetition, together with additional symbols for quinary groupings, was used to indicate how many of each power of 10 were present. For example, MDCCCCLXXXV means 1000 + 500 + 400 + 50 + 30 + 5 = 1985. The familiar abbreviations such as IV for 4 were not used by the Romans. The Chinese system, which is still in use, is similar except that instead of repetition, symbols for the numbers 1 through 9 are used to modify each power of 10. These systems allowed easy transcription of numbers to an abacus for calculation, although they are not convenient for calculation with pencil and paper.
Large numbers cannot be conveniently represented by such systems. The positional notation used worldwide today requires a key idea: the representation of zero by a symbol. As far as we know, this was first used by the Babylonians about 300 B.C. Our decimal positional system was developed in India around 600 A.D. and was used for centuries by the Arabs in the Middle East before being passed on to Europe during the period 12001600hence the name Arabic numerals. This decimal, or base 10, system requires 10 symbols, representing the numbers 0 through 9. The system is called positional (or place-value) because the meaning of the number is understood from the position of the symbols, or digits, of the number. Zero is needed, for example, to distinguish 601 from 61. The reason for the decimal choice is the simple biological fact that humans have 10 fingers and thumbs. Indeed, the word digit derives from the Latin word for finger. Other positional systems developed by ancient peoples include the base 60 system used by the Babylonians, the vestiges of which are still seen today in our division of the hour into 60 minutes and the minute into 60 seconds, and the base 20 system developed by the Mayans, which was used for astronomical calculations. The Mayans are the only people known to have invented the positional number system, with its

CS: assignmentchef QQ: 1823890830 Email: [email protected]