Computer Arithmetic and Validity
Theory, Implementation, and Applications
1st Edition
Published on 17. April 2013
Book
Hardback
XXII, 434 pages
978-3-11-030173-1 (ISBN)
Description
This is the revised and extended second edition of the successful basic book on computer arithmetic. It is consistent with the newest recent standard developments in the field. The book shows how the arithmetic and mathematical capability of the digital computer can be enhanced in a quite natural way. The work is motivated by the desire and the need to improve the accuracy of numerical computing and to control the quality of the computed results (validity). The accuracy requirements for the elementary floating-point operations are extended to the customary product spaces of computations including interval spaces. The mathematical properties of these models are extracted into an axiomatic approach which leads to a general theory of computer arithmetic. Detailed methods and circuits for the implementation of this advanced computer arithmetic on digital computers are developed in part two of the book. Part three then illustrates by a number of sample applications how this extended computer arithmetic can be used to compute highly accurate and mathematically verified results. The book can be used as a high-level undergraduate textbook but also as reference work for research in computer arithmetic and applied mathematics.
Reviews / Votes
Review for the first edition: "The book deals with the theory of computer arithmetic, the implementation of arithmetic on computers, and principles of verified computing. These items are at the same time the titles of the three main parts in which the very informative and highly interesting monograph of 400 pages is divided. [...] an important book which should be read by everyone who does not merely apply a computer uncritically as a black box, but wants to know how it, works, and is interested in how it could work better. [Günter Mayer (Rostock) in ZenralblattMath]More details
Series
Language
English
Place of publication
Berlin/Boston
Germany
Target group
Professional and scholarly
US School Grade: College Graduate Student
Illustrations
34 s/w Tabellen, 101 Abbildungen
101 ill., 34 tbl.
Dimensions
Height: 246 mm
Width: 175 mm
Thickness: 37 mm
Weight
1041 gr
ISBN-13
978-3-11-030173-1 (9783110301731)
Schweitzer Classification
Other editions
Additional editions
E-Book
04/2013
1st Edition
De Gruyter
€174.95
Available for download
Previous edition
Book
05/2008
1st Edition
De Gruyter
€129.95
Article exhausted; check for reprint
Person
Ulrich Kulisch, University Karlsruhe, Germany.
Content
Foreword to the second edition
Preface
Introduction
I Theory of computer arithmetic
1 First concepts
1.1 Ordered sets
1.2 Complete lattices and complete subnets
1.3 Screens and roundings
1.4 Arithmetic operations and roundings
2 Ringoids and vectoids
2.1 Ringoids
2.2 Vectoids
3 Definition of computer arithmetic
3.1 Introduction
3.2 Preliminaries
3.3 The traditional definition of computer arithmetic
3.4 Definition of computer arithmetic by semimorphisms
3.5 A remark about roundings
3.6 Uniqueness of theminus operator
3.7 Rounding near zero
4 Interval arithmetic
4.1 Interval sets and arithmetic
4.2 Interval arithmetic over a linearly ordered set
4.3 Interval matrices
4.4 Interval vectors
4.5 Interval arithmetic on a screen
4.6 Interval matrices and interval vectors on a screen
4.7 Complex interval arithmetic
4.8 Complex intervalmatrices and interval vectors
4.9 Extended interval arithmetic
4.10 Exception-free arithmetic for extended intervals
4.11 Extended interval arithmetic on the computer
4.12 Exception-free arithmetic for closed real intervals on the computer
4.13 Comparison relations and lattice operations
4.14 Algorithmic implementation of interval multiplication and division
II Implementation of arithmetic on computers
5 Floating-point arithmetic
5.1 Definition and properties of the real numbers
5.2 Floating-point numbers and roundings
5.3 Floating-point operations
5.4 Subnormal floating-point numbers
5.5 On the IEEE floating-point arithmetic standard
6 Implementation of floating-point arithmetic on a computer
6.1 A brief review of the realization of integer arithmetic
6.2 Introductory remarks about the level 1 operations
6.3 Addition and subtraction
6.4 Normalization
6.5 Multiplication
6.6 Division
6.7 Rounding
6.8 A universal rounding unit
6.9 Overflow and underflow treatment
6.10 Algorithms using the short accumulator
6.11 The level 2 operations
7 Hardware support for interval arithmetic
7.1 Introduction
7.2 Arithmetic interval operations
7.2.1 Algebraic operations
7.2.2 Comments on the algebraic operations
7.3 Circuitry for the arithmetic interval operations
7.4 Comparisons and lattice operations
7.4.1 Comments on comparisons and lattice operations
7.4.2 Hardware support for comparisons and lattice operations
7.5 Alternative circuitry for interval operations and comparisons
7.5.1 Hardware support for interval arithmetic on x86-processors
7.5.2 Accurate evaluation of interval scalar products
8 Scalar products and complete arithmetic
8.1 Introduction and motivation
8.2 Historical remarks
8.3 The ubiquity of the scalar product in numerical analysis
8.4 Implementation principles
8.4.1 Long adder and long shift
8.4.2 Short adderwith localmemory on the arithmetic unit
8.4.3 Remarks
8.4.4 Fast carry resolution
8.5 Informal sketch for computing an exact dot product
8.6 Scalar product computation units (SPUs)
8.6.1 SPU for computerswith a 32 bit data bus
8.6.2 A coprocessor chip for the exact scalar product
8.6.3 SPU for computerswith a 64 bit data bus
8.7 Comments
8.7.1 Rounding
8.7.2 How much local memory should be provided on an SPU?
8.8 The data format complete and complete arithmetic
8.8.1 Low level instructions for complete arithmetic
8.8.2 Complete arithmetic in high level programming languages
8.9 Top speed scalar product units
8.9.1 SPU with long adder for 64 bit data word
8.9.2 SPU with long adder for 32 bit data word
8.9.3 An FPGA coprocessor for the exact scalar product
8.9.4 SPU with short adder and complete register
8.9.5 Carry-free accumulation of products in redundant arithmetic
8.10 Hardware complete register window
III Principles of verified computing
9 Sample applications
9.1 Basic properties of interval mathematics
9.1.1 Interval arithmetic, a powerful calculus to deal with inequalities
9.1.2 Interval arithmetic as executable set operations
9.1.3 Enclosing the range of function values
9.1.4 Nonzero property of a function, global optimization
9.2 Differentiation arithmetic, enclosures of derivatives
9.3 The interval Newton method
9.4 The extended interval Newton method
9.5 Verified solution of systems of linear equations
9.6 Accurate evaluation of arithmetic expressions
9.6.1 Complete expressions
9.6.2 Accurate evaluation of polynomials
9.6.3 Arithmetic expressions
9.7 Multiple precision arithmetics
9.7.1 Multiple precision floating-point arithmetic
9.7.2 Multiple precision interval arithmetic
9.7.3 Applications
9.7.4 Adding an exponent part as a scaling factor to complete arithmetic
9.8 Remarks onKaucher arithmetic
9.8.1 The basic operations ofKaucher arithmetic
A Frequently used symbols
B On homomorphism
Bibliography
List of figures
List of tables
Index
Preface
Introduction
I Theory of computer arithmetic
1 First concepts
1.1 Ordered sets
1.2 Complete lattices and complete subnets
1.3 Screens and roundings
1.4 Arithmetic operations and roundings
2 Ringoids and vectoids
2.1 Ringoids
2.2 Vectoids
3 Definition of computer arithmetic
3.1 Introduction
3.2 Preliminaries
3.3 The traditional definition of computer arithmetic
3.4 Definition of computer arithmetic by semimorphisms
3.5 A remark about roundings
3.6 Uniqueness of theminus operator
3.7 Rounding near zero
4 Interval arithmetic
4.1 Interval sets and arithmetic
4.2 Interval arithmetic over a linearly ordered set
4.3 Interval matrices
4.4 Interval vectors
4.5 Interval arithmetic on a screen
4.6 Interval matrices and interval vectors on a screen
4.7 Complex interval arithmetic
4.8 Complex intervalmatrices and interval vectors
4.9 Extended interval arithmetic
4.10 Exception-free arithmetic for extended intervals
4.11 Extended interval arithmetic on the computer
4.12 Exception-free arithmetic for closed real intervals on the computer
4.13 Comparison relations and lattice operations
4.14 Algorithmic implementation of interval multiplication and division
II Implementation of arithmetic on computers
5 Floating-point arithmetic
5.1 Definition and properties of the real numbers
5.2 Floating-point numbers and roundings
5.3 Floating-point operations
5.4 Subnormal floating-point numbers
5.5 On the IEEE floating-point arithmetic standard
6 Implementation of floating-point arithmetic on a computer
6.1 A brief review of the realization of integer arithmetic
6.2 Introductory remarks about the level 1 operations
6.3 Addition and subtraction
6.4 Normalization
6.5 Multiplication
6.6 Division
6.7 Rounding
6.8 A universal rounding unit
6.9 Overflow and underflow treatment
6.10 Algorithms using the short accumulator
6.11 The level 2 operations
7 Hardware support for interval arithmetic
7.1 Introduction
7.2 Arithmetic interval operations
7.2.1 Algebraic operations
7.2.2 Comments on the algebraic operations
7.3 Circuitry for the arithmetic interval operations
7.4 Comparisons and lattice operations
7.4.1 Comments on comparisons and lattice operations
7.4.2 Hardware support for comparisons and lattice operations
7.5 Alternative circuitry for interval operations and comparisons
7.5.1 Hardware support for interval arithmetic on x86-processors
7.5.2 Accurate evaluation of interval scalar products
8 Scalar products and complete arithmetic
8.1 Introduction and motivation
8.2 Historical remarks
8.3 The ubiquity of the scalar product in numerical analysis
8.4 Implementation principles
8.4.1 Long adder and long shift
8.4.2 Short adderwith localmemory on the arithmetic unit
8.4.3 Remarks
8.4.4 Fast carry resolution
8.5 Informal sketch for computing an exact dot product
8.6 Scalar product computation units (SPUs)
8.6.1 SPU for computerswith a 32 bit data bus
8.6.2 A coprocessor chip for the exact scalar product
8.6.3 SPU for computerswith a 64 bit data bus
8.7 Comments
8.7.1 Rounding
8.7.2 How much local memory should be provided on an SPU?
8.8 The data format complete and complete arithmetic
8.8.1 Low level instructions for complete arithmetic
8.8.2 Complete arithmetic in high level programming languages
8.9 Top speed scalar product units
8.9.1 SPU with long adder for 64 bit data word
8.9.2 SPU with long adder for 32 bit data word
8.9.3 An FPGA coprocessor for the exact scalar product
8.9.4 SPU with short adder and complete register
8.9.5 Carry-free accumulation of products in redundant arithmetic
8.10 Hardware complete register window
III Principles of verified computing
9 Sample applications
9.1 Basic properties of interval mathematics
9.1.1 Interval arithmetic, a powerful calculus to deal with inequalities
9.1.2 Interval arithmetic as executable set operations
9.1.3 Enclosing the range of function values
9.1.4 Nonzero property of a function, global optimization
9.2 Differentiation arithmetic, enclosures of derivatives
9.3 The interval Newton method
9.4 The extended interval Newton method
9.5 Verified solution of systems of linear equations
9.6 Accurate evaluation of arithmetic expressions
9.6.1 Complete expressions
9.6.2 Accurate evaluation of polynomials
9.6.3 Arithmetic expressions
9.7 Multiple precision arithmetics
9.7.1 Multiple precision floating-point arithmetic
9.7.2 Multiple precision interval arithmetic
9.7.3 Applications
9.7.4 Adding an exponent part as a scaling factor to complete arithmetic
9.8 Remarks onKaucher arithmetic
9.8.1 The basic operations ofKaucher arithmetic
A Frequently used symbols
B On homomorphism
Bibliography
List of figures
List of tables
Index