Computer Arithmetic and Validity (eBook)

lt;!doctype html public "-//w3c//dtd html 4.0 transitional//en">

Ulrich Kulisch, University Karlsruhe, Germany.

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

lt;!doctype html public "-//w3c//dtd html 4.0 transitional//en">

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]