Computer Arithmetic and Validity
Theory, Implementation, and Applications
1st Edition
Published on 30. April 2013
XXII, 434 pages
978-3-11-030179-3 (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
101 Abbildungen, 34 s/w Tabellen
101 ill., 34 tbl.
File size
3,30 MB
ISBN-13
978-3-11-030179-3 (9783110301793)
DOI
http://www.degruyter.com/isbn/9783110301793
Schweitzer Classification
Other editions
Additional editions
Book
04/2013
1st Edition
De Gruyter
€174.95
Shipment within 7-9 days
Person
Ulrich Kulisch, University Karlsruhe, Germany.
Content
1 - Foreword to the second edition [Seite 7]
2 - Preface [Seite 9]
3 - Introduction [Seite 23]
4 - I Theory of computer arithmetic [Seite 33]
4.1 - 1 First concepts [Seite 35]
4.1.1 - 1.1 Ordered sets [Seite 35]
4.1.2 - 1.2 Complete lattices and complete subnets [Seite 40]
4.1.3 - 1.3 Screens and roundings [Seite 46]
4.1.4 - 1.4 Arithmetic operations and roundings [Seite 57]
4.2 - 2 Ringoids and vectoids [Seite 65]
4.2.1 - 2.1 Ringoids [Seite 65]
4.2.2 - 2.2 Vectoids [Seite 76]
4.3 - 3 Definition of computer arithmetic [Seite 84]
4.3.1 - 3.1 Introduction [Seite 84]
4.3.2 - 3.2 Preliminaries [Seite 87]
4.3.3 - 3.3 The traditional definition of computer arithmetic [Seite 91]
4.3.4 - 3.4 Definition of computer arithmetic by semimorphisms [Seite 92]
4.3.5 - 3.5 A remark about roundings [Seite 100]
4.3.6 - 3.6 Uniqueness of the minus operator [Seite 101]
4.3.7 - 3.7 Rounding near zero [Seite 103]
4.4 - 4 Interval arithmetic [Seite 109]
4.4.1 - 4.1 Interval sets and arithmetic [Seite 110]
4.4.2 - 4.2 Interval arithmetic over a linearly ordered set [Seite 119]
4.4.3 - 4.3 Interval matrices [Seite 123]
4.4.4 - 4.4 Interval vectors [Seite 129]
4.4.5 - 4.5 Interval arithmetic on a screen [Seite 132]
4.4.6 - 4.6 Interval matrices and interval vectors on a screen [Seite 140]
4.4.7 - 4.7 Complex interval arithmetic [Seite 148]
4.4.8 - 4.8 Complex interval matrices and interval vectors [Seite 154]
4.4.9 - 4.9 Extended interval arithmetic [Seite 159]
4.4.10 - 4.10 Exception-free arithmetic for extended intervals [Seite 163]
4.4.11 - 4.11 Extended interval arithmetic on the computer [Seite 168]
4.4.12 - 4.12 Exception-free arithmetic for closed real intervals on the computer [Seite 171]
4.4.13 - 4.13 Comparison relations and lattice operations [Seite 174]
4.4.14 - 4.14 Algorithmic implementation of interval multiplication and division [Seite 175]
5 - II Implementation of arithmetic on computers [Seite 177]
5.1 - 5 Floating-point arithmetic [Seite 179]
5.1.1 - 5.1 Definition and properties of the real numbers [Seite 179]
5.1.2 - 5.2 Floating-point numbers and roundings [Seite 185]
5.1.3 - 5.3 Floating-point operations [Seite 194]
5.1.4 - 5.4 Subnormal floating-point numbers [Seite 202]
5.1.5 - 5.5 On the IEEE floating-point arithmetic standard [Seite 203]
5.2 - 6 Implementation of floating-point arithmetic on a computer [Seite 213]
5.2.1 - 6.1 A brief review of the realization of integer arithmetic [Seite 214]
5.2.2 - 6.2 Introductory remarks about the level 1 operations [Seite 223]
5.2.3 - 6.3 Addition and subtraction [Seite 228]
5.2.4 - 6.4 Normalization [Seite 232]
5.2.5 - 6.5 Multiplication [Seite 234]
5.2.6 - 6.6 Division [Seite 234]
5.2.7 - 6.7 Rounding [Seite 236]
5.2.8 - 6.8 A universal rounding unit [Seite 238]
5.2.9 - 6.9 Overflow and underflow treatment [Seite 239]
5.2.10 - 6.10 Algorithms using the short accumulator [Seite 242]
5.2.11 - 6.11 The level 2 operations [Seite 248]
5.3 - 7 Hardware support for interval arithmetic [Seite 258]
5.3.1 - 7.1 Introduction [Seite 258]
5.3.2 - 7.2 Arithmetic interval operations [Seite 259]
5.3.2.1 - 7.2.1 Algebraic operations [Seite 260]
5.3.2.2 - 7.2.2 Comments on the algebraic operations [Seite 262]
5.3.3 - 7.3 Circuitry for the arithmetic interval operations [Seite 263]
5.3.4 - 7.4 Comparisons and lattice operations [Seite 264]
5.3.4.1 - 7.4.1 Comments on comparisons and lattice operations [Seite 265]
5.3.4.2 - 7.4.2 Hardware support for comparisons and lattice operations [Seite 265]
5.3.5 - 7.5 Alternative circuitry for interval operations and comparisons [Seite 266]
5.3.5.1 - 7.5.1 Hardware support for interval arithmetic on x86-processors [Seite 267]
5.3.5.2 - 7.5.2 Accurate evaluation of interval scalar products [Seite 269]
5.4 - 8 Scalar products and complete arithmetic [Seite 271]
5.4.1 - 8.1 Introduction and motivation [Seite 272]
5.4.2 - 8.2 Historical remarks [Seite 274]
5.4.3 - 8.3 The ubiquity of the scalar product in numerical analysis [Seite 279]
5.4.4 - 8.4 Implementation principles [Seite 282]
5.4.4.1 - 8.4.1 Long adder and long shift [Seite 284]
5.4.4.2 - 8.4.2 Short adder with local memory on the arithmetic unit [Seite 284]
5.4.4.3 - 8.4.3 Remarks [Seite 285]
5.4.4.4 - 8.4.4 Fast carry resolution [Seite 287]
5.4.5 - 8.5 Informal sketch for computing an exact dot product [Seite 289]
5.4.6 - 8.6 Scalar product computation units (SPUs) [Seite 289]
5.4.6.1 - 8.6.1 SPU for computers with a 32 bit data bus [Seite 291]
5.4.6.2 - 8.6.2 A coprocessor chip for the exact scalar product [Seite 294]
5.4.6.3 - 8.6.3 SPU for computers with a 64 bit data bus [Seite 297]
5.4.7 - 8.7 Comments [Seite 300]
5.4.7.1 - 8.7.1 Rounding [Seite 300]
5.4.7.2 - 8.7.2 How much local memory should be provided on an SPU? [Seite 301]
5.4.8 - 8.8 The data format complete and complete arithmetic [Seite 303]
5.4.8.1 - 8.8.1 Low level instructions for complete arithmetic [Seite 304]
5.4.8.2 - 8.8.2 Complete arithmetic in high level programming languages [Seite 305]
5.4.9 - 8.9 Top speed scalar product units [Seite 309]
5.4.9.1 - 8.9.1 SPU with long adder for 64 bit data word [Seite 309]
5.4.9.2 - 8.9.2 SPU with long adder for 32 bit data word [Seite 314]
5.4.9.3 - 8.9.3 An FPGA coprocessor for the exact scalar product [Seite 317]
5.4.9.4 - 8.9.4 SPU with short adder and complete register [Seite 317]
5.4.9.5 - 8.9.5 Carry-free accumulation of products in redundant arithmetic [Seite 323]
5.4.10 - 8.10 Hardware complete register window [Seite 324]
6 - III Principles of verified computing [Seite 327]
6.1 - 9 Sample applications [Seite 329]
6.1.1 - 9.1 Basic properties of interval mathematics [Seite 331]
6.1.1.1 - 9.1.1 Interval arithmetic, a powerful calculus to deal with inequalities [Seite 331]
6.1.1.2 - 9.1.2 Interval arithmetic as executable set operations [Seite 332]
6.1.1.3 - 9.1.3 Enclosing the range of function values [Seite 338]
6.1.1.4 - 9.1.4 Nonzero property of a function, global optimization [Seite 341]
6.1.2 - 9.2 Differentiation arithmetic, enclosures of derivatives [Seite 343]
6.1.3 - 9.3 The interval Newton method [Seite 351]
6.1.4 - 9.4 The extended interval Newton method [Seite 354]
6.1.5 - 9.5 Verified solution of systems of linear equations [Seite 355]
6.1.6 - 9.6 Accurate evaluation of arithmetic expressions [Seite 362]
6.1.6.1 - 9.6.1 Complete expressions [Seite 363]
6.1.6.2 - 9.6.2 Accurate evaluation of polynomials [Seite 364]
6.1.6.3 - 9.6.3 Arithmetic expressions [Seite 368]
6.1.7 - 9.7 Multiple precision arithmetics [Seite 369]
6.1.7.1 - 9.7.1 Multiple precision floating-point arithmetic [Seite 370]
6.1.7.2 - 9.7.2 Multiple precision interval arithmetic [Seite 373]
6.1.7.3 - 9.7.3 Applications [Seite 378]
6.1.7.4 - 9.7.4 Adding an exponent part as a scaling factor to complete arithmetic [Seite 380]
6.1.8 - 9.8 Remarks on Kaucher arithmetic [Seite 382]
6.1.8.1 - 9.8.1 The basic operations of Kaucher arithmetic [Seite 386]
7 - A Frequently used symbols [Seite 389]
8 - B On homomorphism [Seite 391]
9 - Bibliography [Seite 393]
10 - List of figures [Seite 443]
11 - List of tables [Seite 447]
12 - Index [Seite 449]
2 - Preface [Seite 9]
3 - Introduction [Seite 23]
4 - I Theory of computer arithmetic [Seite 33]
4.1 - 1 First concepts [Seite 35]
4.1.1 - 1.1 Ordered sets [Seite 35]
4.1.2 - 1.2 Complete lattices and complete subnets [Seite 40]
4.1.3 - 1.3 Screens and roundings [Seite 46]
4.1.4 - 1.4 Arithmetic operations and roundings [Seite 57]
4.2 - 2 Ringoids and vectoids [Seite 65]
4.2.1 - 2.1 Ringoids [Seite 65]
4.2.2 - 2.2 Vectoids [Seite 76]
4.3 - 3 Definition of computer arithmetic [Seite 84]
4.3.1 - 3.1 Introduction [Seite 84]
4.3.2 - 3.2 Preliminaries [Seite 87]
4.3.3 - 3.3 The traditional definition of computer arithmetic [Seite 91]
4.3.4 - 3.4 Definition of computer arithmetic by semimorphisms [Seite 92]
4.3.5 - 3.5 A remark about roundings [Seite 100]
4.3.6 - 3.6 Uniqueness of the minus operator [Seite 101]
4.3.7 - 3.7 Rounding near zero [Seite 103]
4.4 - 4 Interval arithmetic [Seite 109]
4.4.1 - 4.1 Interval sets and arithmetic [Seite 110]
4.4.2 - 4.2 Interval arithmetic over a linearly ordered set [Seite 119]
4.4.3 - 4.3 Interval matrices [Seite 123]
4.4.4 - 4.4 Interval vectors [Seite 129]
4.4.5 - 4.5 Interval arithmetic on a screen [Seite 132]
4.4.6 - 4.6 Interval matrices and interval vectors on a screen [Seite 140]
4.4.7 - 4.7 Complex interval arithmetic [Seite 148]
4.4.8 - 4.8 Complex interval matrices and interval vectors [Seite 154]
4.4.9 - 4.9 Extended interval arithmetic [Seite 159]
4.4.10 - 4.10 Exception-free arithmetic for extended intervals [Seite 163]
4.4.11 - 4.11 Extended interval arithmetic on the computer [Seite 168]
4.4.12 - 4.12 Exception-free arithmetic for closed real intervals on the computer [Seite 171]
4.4.13 - 4.13 Comparison relations and lattice operations [Seite 174]
4.4.14 - 4.14 Algorithmic implementation of interval multiplication and division [Seite 175]
5 - II Implementation of arithmetic on computers [Seite 177]
5.1 - 5 Floating-point arithmetic [Seite 179]
5.1.1 - 5.1 Definition and properties of the real numbers [Seite 179]
5.1.2 - 5.2 Floating-point numbers and roundings [Seite 185]
5.1.3 - 5.3 Floating-point operations [Seite 194]
5.1.4 - 5.4 Subnormal floating-point numbers [Seite 202]
5.1.5 - 5.5 On the IEEE floating-point arithmetic standard [Seite 203]
5.2 - 6 Implementation of floating-point arithmetic on a computer [Seite 213]
5.2.1 - 6.1 A brief review of the realization of integer arithmetic [Seite 214]
5.2.2 - 6.2 Introductory remarks about the level 1 operations [Seite 223]
5.2.3 - 6.3 Addition and subtraction [Seite 228]
5.2.4 - 6.4 Normalization [Seite 232]
5.2.5 - 6.5 Multiplication [Seite 234]
5.2.6 - 6.6 Division [Seite 234]
5.2.7 - 6.7 Rounding [Seite 236]
5.2.8 - 6.8 A universal rounding unit [Seite 238]
5.2.9 - 6.9 Overflow and underflow treatment [Seite 239]
5.2.10 - 6.10 Algorithms using the short accumulator [Seite 242]
5.2.11 - 6.11 The level 2 operations [Seite 248]
5.3 - 7 Hardware support for interval arithmetic [Seite 258]
5.3.1 - 7.1 Introduction [Seite 258]
5.3.2 - 7.2 Arithmetic interval operations [Seite 259]
5.3.2.1 - 7.2.1 Algebraic operations [Seite 260]
5.3.2.2 - 7.2.2 Comments on the algebraic operations [Seite 262]
5.3.3 - 7.3 Circuitry for the arithmetic interval operations [Seite 263]
5.3.4 - 7.4 Comparisons and lattice operations [Seite 264]
5.3.4.1 - 7.4.1 Comments on comparisons and lattice operations [Seite 265]
5.3.4.2 - 7.4.2 Hardware support for comparisons and lattice operations [Seite 265]
5.3.5 - 7.5 Alternative circuitry for interval operations and comparisons [Seite 266]
5.3.5.1 - 7.5.1 Hardware support for interval arithmetic on x86-processors [Seite 267]
5.3.5.2 - 7.5.2 Accurate evaluation of interval scalar products [Seite 269]
5.4 - 8 Scalar products and complete arithmetic [Seite 271]
5.4.1 - 8.1 Introduction and motivation [Seite 272]
5.4.2 - 8.2 Historical remarks [Seite 274]
5.4.3 - 8.3 The ubiquity of the scalar product in numerical analysis [Seite 279]
5.4.4 - 8.4 Implementation principles [Seite 282]
5.4.4.1 - 8.4.1 Long adder and long shift [Seite 284]
5.4.4.2 - 8.4.2 Short adder with local memory on the arithmetic unit [Seite 284]
5.4.4.3 - 8.4.3 Remarks [Seite 285]
5.4.4.4 - 8.4.4 Fast carry resolution [Seite 287]
5.4.5 - 8.5 Informal sketch for computing an exact dot product [Seite 289]
5.4.6 - 8.6 Scalar product computation units (SPUs) [Seite 289]
5.4.6.1 - 8.6.1 SPU for computers with a 32 bit data bus [Seite 291]
5.4.6.2 - 8.6.2 A coprocessor chip for the exact scalar product [Seite 294]
5.4.6.3 - 8.6.3 SPU for computers with a 64 bit data bus [Seite 297]
5.4.7 - 8.7 Comments [Seite 300]
5.4.7.1 - 8.7.1 Rounding [Seite 300]
5.4.7.2 - 8.7.2 How much local memory should be provided on an SPU? [Seite 301]
5.4.8 - 8.8 The data format complete and complete arithmetic [Seite 303]
5.4.8.1 - 8.8.1 Low level instructions for complete arithmetic [Seite 304]
5.4.8.2 - 8.8.2 Complete arithmetic in high level programming languages [Seite 305]
5.4.9 - 8.9 Top speed scalar product units [Seite 309]
5.4.9.1 - 8.9.1 SPU with long adder for 64 bit data word [Seite 309]
5.4.9.2 - 8.9.2 SPU with long adder for 32 bit data word [Seite 314]
5.4.9.3 - 8.9.3 An FPGA coprocessor for the exact scalar product [Seite 317]
5.4.9.4 - 8.9.4 SPU with short adder and complete register [Seite 317]
5.4.9.5 - 8.9.5 Carry-free accumulation of products in redundant arithmetic [Seite 323]
5.4.10 - 8.10 Hardware complete register window [Seite 324]
6 - III Principles of verified computing [Seite 327]
6.1 - 9 Sample applications [Seite 329]
6.1.1 - 9.1 Basic properties of interval mathematics [Seite 331]
6.1.1.1 - 9.1.1 Interval arithmetic, a powerful calculus to deal with inequalities [Seite 331]
6.1.1.2 - 9.1.2 Interval arithmetic as executable set operations [Seite 332]
6.1.1.3 - 9.1.3 Enclosing the range of function values [Seite 338]
6.1.1.4 - 9.1.4 Nonzero property of a function, global optimization [Seite 341]
6.1.2 - 9.2 Differentiation arithmetic, enclosures of derivatives [Seite 343]
6.1.3 - 9.3 The interval Newton method [Seite 351]
6.1.4 - 9.4 The extended interval Newton method [Seite 354]
6.1.5 - 9.5 Verified solution of systems of linear equations [Seite 355]
6.1.6 - 9.6 Accurate evaluation of arithmetic expressions [Seite 362]
6.1.6.1 - 9.6.1 Complete expressions [Seite 363]
6.1.6.2 - 9.6.2 Accurate evaluation of polynomials [Seite 364]
6.1.6.3 - 9.6.3 Arithmetic expressions [Seite 368]
6.1.7 - 9.7 Multiple precision arithmetics [Seite 369]
6.1.7.1 - 9.7.1 Multiple precision floating-point arithmetic [Seite 370]
6.1.7.2 - 9.7.2 Multiple precision interval arithmetic [Seite 373]
6.1.7.3 - 9.7.3 Applications [Seite 378]
6.1.7.4 - 9.7.4 Adding an exponent part as a scaling factor to complete arithmetic [Seite 380]
6.1.8 - 9.8 Remarks on Kaucher arithmetic [Seite 382]
6.1.8.1 - 9.8.1 The basic operations of Kaucher arithmetic [Seite 386]
7 - A Frequently used symbols [Seite 389]
8 - B On homomorphism [Seite 391]
9 - Bibliography [Seite 393]
10 - List of figures [Seite 443]
11 - List of tables [Seite 447]
12 - Index [Seite 449]
