Computer arithmetic and validity : theory, implementation, and applications

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. Cover 1 Title 4 Copyright 5 Foreword to the second edition 8 Preface 10 Contents 20 Introduction 24 Part I. Theory of computer arithmetic 34 Chapter 1. First concepts 34 1.1 Ordered sets 34 1.2 Complete lattices and complete subnets 39 1.3 Screens and roundings 45 1.4 Arithmetic operations and roundings 56 Chapter 2. Ringoids and vectoids 64 2.1 Ringoids 64 2.2 Vectoids 75 Chapter 3. Definition of computer arithmetic 83 3.1 Introduction 83 3.2 Preliminaries 86 3.3 The traditional definition of computer arithmetic 90 3.4 Definition of computer arithmetic by semimorphisms 91 3.5 A remark about roundings 99 3.6 Uniqueness of the minus operator 100 3.7 Rounding near zero 102 Chapter 4. Interval arithmetic 108 4.1 Interval sets and arithmetic 109 4.2 Interval arithmetic over a linearly ordered set 118 4.3 Interval matrices 122 4.4 Interval vectors 128 4.5 Interval arithmetic on a screen 131 4.6 Interval matrices and interval vectors on a screen 139 4.7 Complex interval arithmetic 147 4.8 Complex interval matrices and interval vectors 153 4.9 Extended interval arithmetic 158 4.10 Exception-free arithmetic for extended intervals 162 4.11 Extended interval arithmetic on the computer 167 4.12 Exception-free arithmetic for closed real intervals on the computer 170 4.13 Comparison relations and lattice operations 173 4.14 Algorithmic implementation of interval multiplication and division 174 Part II. Implementation of arithmetic on computers 176 Chapter 5. Floating-point arithmetic 176 5.1 Definition and properties of the real numbers 176 5.2 Floating-point numbers and roundings 182 5.3 Floating-point operations 191 5.4 Subnormal floating-point numbers 199 5.5 On the IEEE floating-point arithmetic standard 200 Chapter 6. Implementation of floating-point arithmetic on a computer 210 6.1 A brief review of the realization of integer arithmetic 211 6.2 Introductory remarks about the level 1 operations 220 6.3 Addition and subtraction 225 6.4 Normalization 229 6.5 Multiplication 231 6.6 Division 231 6.7 Rounding 233 6.8 A universal rounding unit 235 6.9 Overflow and underflow treatment 236 6.10 Algorithms using the short accumulator 239 6.11 The level 2 operations 245 Chapter 7. Hardware support for interval arithmetic 255 7.1 Introduction 255 7.2 Arithmetic interval operations 256 7.2.1 Algebraic operations 257 7.2.2 Comments on the algebraic operations 259 7.3 Circuitry for the arithmetic interval operations 260 7.4 Comparisons and lattice operations 261 7.4.1 Comments on comparisons and lattice operations 262 7.4.2 Hardware support for comparisons and lattice operations 262 7.5 Alternative circuitry for interval operations and comparisons 263 7.5.1 Hardware support for interval arithmetic on x86-processors 264 7.5.2 Accurate evaluation of interval scalar products 266 Chapter 8. Scalar products and complete arithmetic 268 8.1 Introduction and motivation 269 8.2 Historical remarks 271 8.3 The ubiquity of the scalar product in numerical analysis 276 8.4 Implementation principles 279 8.4.1 Long adder and long shift 281 8.4.2 Short adder with local memory on the arithmetic unit 281 8.4.3 Remarks 282 8.4.4 Fast carry resolution 284 8.5 Informal sketch for computing an exact dot product 286 8.6 Scalar product computation units (SPUs) 286 8.6.1 SPU for computers with a 32 bit data bus 288 8.6.2 A coprocessor chip for the exact scalar product 291 8.6.3 SPU for computers with a 64 bit data bus 294 8.7 Comments 297 8.7.1 Rounding 297 8.7.2 How much local memory should be provided on an SPU? 298 8.8 The data format complete and complete arithmetic 300 8.8.1 Low level instructions for complete arithmetic 301 8.8.2 Complete arithmetic in high level programming languages 302 8.9 Top speed scalar product units 306 8.9.1 SPU with long adder for 64 bit data word 306 8.9.2 SPU with long adder for 32 bit data word 311 8.9.3 An FPGA coprocessor for the exact scalar product 314 8.9.4 SPU with short adder and complete register 314 8.9.5 Carry-free accumulation of products in redundant arithmetic 320 8.10 Hardware complete register window 321 Part III. Principles of verified computing 324 Chapter 9. Sample applications 324 9.1 Basic properties of interval mathematics 326 9.1.1 Interval arithmetic, a powerful calculus to deal with inequalities 326 9.1.2 Interval arithmetic as executable set operations 327 9.1.3 Enclosing the range of function values 333 9.1.4 Nonzero property of a function, global optimization 336 9.2 Differentiation arithmetic, enclosures of derivatives 338 9.3 The interval Newton method 346 9.4 The extended interval Newton method 349 9.5 Verified solution of systems of linear equations 350 9.6 Accurate evaluation of arithmetic expressions 357 9.6.1 Complete expressions 358 9.6.2 Accurate evaluation of polynomials 359 9.6.3 Arithmetic expressions 363 9.7 Multiple precision arithmetics 364 9.7.1 Multiple precision floating-point arithmetic 365 9.7.2 Multiple precision interval arithmetic 368 9.7.3 Applications 373 9.7.4 Adding an exponent part as a scaling factor to complete arithmetic 375 9.8 Remarks on Kaucher arithmetic 377 9.8.1 The basic operations of Kaucher arithmetic 381 Appendix A. Frequently used symbols 384 Appendix B. On homomorphism 386 Bibliography 388 List of figures 438 List of tables 442 Index 444 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 capability of the computer can be enhanced. 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 and lead to a general theory of computer arithmetic. Detailed methods and circuits for the implementation of this advanced computer arithmetic are developed in the book. It illustrates how the extended 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 Focuses on computer arithmetic. This book shows how the arithmetic capability of the computer can be enhanced. It illustrates how the extended arithmetic can be used to compute highly accurate and mathematically verified results.