Kulisch Computer Arithmetic and Validity

Theory, Implementation, and Applications
1. Auflage 2013
ISBN: 978-3-11-030179-3
Verlag: De Gruyter
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 33, 456 Seiten

Reihe: De Gruyter Studies in MathematicsISSN

Autoren/Hrsg.

Kulisch, Ulrich

Fachgebiete

• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen
• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker

Inhaltsverzeichnis

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

Über Autor(innen)

Ulrich Kulisch, University Karlsruhe, Germany.