| Preface |
|
xi | |
| Introduction |
|
1 | |
| I Theory of Computer Arithmetic |
|
11 | |
|
|
|
12 | |
|
|
|
12 | |
|
1.2 Complete Lattices and Complete Subnets |
|
|
17 | |
|
1.3 Screens and Roundings |
|
|
23 | |
|
1.4 Arithmetic Operations and Roundings |
|
|
34 | |
|
|
|
42 | |
|
|
|
42 | |
|
|
|
53 | |
|
3 Definition of Computer Arithmetic |
|
|
60 | |
|
|
|
60 | |
|
|
|
62 | |
|
3.3 The Traditional Definition of Computer Arithmetic |
|
|
67 | |
|
3.4 Definition of Computer Arithmetic by Semimorphisms |
|
|
69 | |
|
3.5 A Remark About Roundings |
|
|
75 | |
|
3.6 Uniqueness of the Minus Operator |
|
|
77 | |
|
|
|
79 | |
|
|
|
84 | |
|
4.1 Interval Sets and Arithmetic |
|
|
84 | |
|
4.2 Interval Arithmetic Over a Linearly Ordered Set |
|
|
94 | |
|
|
|
98 | |
|
|
|
103 | |
|
4.5 Interval Arithmetic on a Screen |
|
|
106 | |
|
4.6 Interval Matrices and Interval Vectors on a Screen |
|
|
114 | |
|
4.7 Complex Interval Arithmetic |
|
|
122 | |
|
4.8 Complex Interval Matrices and Interval Vectors |
|
|
129 | |
|
4.9 Extended Interval Arithmetic |
|
|
134 | |
|
4.10 Exception-free Arithmetic for Extended Intervals |
|
|
140 | |
|
4.11 Extended Interval Arithmetic on the Computer |
|
|
145 | |
|
4.12 Implementation of Extended Interval Arithmetic |
|
|
149 | |
|
4.13 Comparison Relations and Lattice Operations |
|
|
150 | |
|
4.14 Algorithmic Implementation of Interval Multiplication and Division |
|
|
151 | |
| II Implementation of Arithmetic on Computers |
|
153 | |
|
5 Floating-Point Arithmetic |
|
|
154 | |
|
5.1 Definition and Properties of the Real Numbers |
|
|
154 | |
|
5.2 Floating-Point Numbers and Roundings |
|
|
160 | |
|
5.3 Floating-Point Operations |
|
|
168 | |
|
5.4 Subnormal Floating-Point Numbers |
|
|
177 | |
|
5.5 On the IEEE Floating-Point Arithmetic Standard |
|
|
178 | |
|
6 Implementation of Floating-Point Arithmetic on a Computer |
|
|
187 | |
|
6.1 A Brief Review on the Realization of Integer Arithmetic |
|
|
188 | |
|
6.2 Introductory Remarks About the Level 1 Operations |
|
|
196 | |
|
6.3 Addition and Subtraction |
|
|
201 | |
|
|
|
206 | |
|
|
|
207 | |
|
|
|
208 | |
|
|
|
209 | |
|
6.8 A Universal Rounding Unit |
|
|
211 | |
|
6.9 Overflow and Underflow Treatment |
|
|
213 | |
|
6.10 Algorithms Using the Short Accumulator |
|
|
215 | |
|
6.11 The Level 2 Operations |
|
|
222 | |
|
7 Hardware Support for Interval Arithmetic |
|
|
233 | |
|
|
|
233 | |
|
7.2 An Instruction Set for Interval Arithmetic |
|
|
234 | |
|
7.2.1 Algebraic Operations |
|
|
234 | |
|
7.2.2 Comments on the Algebraic Operations |
|
|
235 | |
|
7.2.3 Comparisons and Lattice Operations |
|
|
236 | |
|
7.2.4 Comments on Comparisons and Lattice Operations |
|
|
236 | |
|
7.3 General Circuitry for Interval Operations and Comparisons |
|
|
236 | |
|
7.3.1 Algebraic Operations |
|
|
236 | |
|
7.3.2 Comparisons and Result-Selection |
|
|
240 | |
|
7.3.3 Alternative Circuitry for Interval Operations and Comparisons |
|
|
241 | |
|
7.3.4 Hardware Support for Interval Arithmetic on X86-Processors |
|
|
243 | |
|
7.3.5 Accurate Evaluation of Interval Scalar Products |
|
|
244 | |
|
8 Scalar Products and Complete Arithmetic |
|
|
245 | |
|
8.1 Introduction and Motivation |
|
|
246 | |
|
|
|
247 | |
|
8.3 The Ubiquity of the Scalar Product in Numerical Analysis |
|
|
252 | |
|
8.4 Implementation Principles |
|
|
256 | |
|
8.4.1 Long Adder and Long Shift |
|
|
257 | |
|
8.4.2 Short Adder with Local Memory on the Arithmetic Unit |
|
|
258 | |
|
|
|
259 | |
|
8.4.4 Fast Carry Resolution |
|
|
261 | |
|
8.5 Scalar Product Computation Units (SPUs) |
|
|
263 | |
|
8.5.1 SPU for Computers with a 32 Bit Data Bus |
|
|
263 | |
|
8.5.2 A Coprocessor Chip for the Exact Scalar Product |
|
|
266 | |
|
8.5.3 SPU for Computers with a 64 Bit Data Bus |
|
|
270 | |
|
|
|
272 | |
|
|
|
272 | |
|
8.6.2 How Much Local Memory Should be Provided on an SPU? |
|
|
274 | |
|
8.7 The Data Format Complete and Complete Arithmetic |
|
|
275 | |
|
8.7.1 Low Level Instructions for Complete Arithmetic |
|
|
277 | |
|
8.7.2 Complete Arithmetic in High Level Programming Languages |
|
|
279 | |
|
8.8 Top Speed Scalar Product Units |
|
|
282 | |
|
8.8.1 SPU with Long Adder for 64 Bit Data Word |
|
|
282 | |
|
8.8.2 SPU with Long Adder for 32 Bit Data Word |
|
|
287 | |
|
8.8.3 A FPGA Coprocessor for the Exact Scalar Product |
|
|
290 | |
|
8.8.4 SPU with Short Adder and Complete Register |
|
|
291 | |
|
8.8.5 Carry-Free Accumulation of Products in Redundant Arithmetic |
|
|
297 | |
|
8.9 Hardware Complete Register Window |
|
|
297 | |
| III Principles of Verified Computing |
|
301 | |
|
|
|
302 | |
|
9.1 Basic Properties of Interval Mathematics |
|
|
304 | |
|
9.1.1 Interval Arithmetic, a Powerful Calculus to Deal with Inequalities |
|
|
304 | |
|
9.1.2 Interval Arithmetic as Executable Set Operations |
|
|
305 | |
|
9.1.3 Enclosing the Range of Function Values |
|
|
311 | |
|
9.1.4 Nonzero Property of a Function, Global Optimization |
|
|
314 | |
|
9.2 Differentiation Arithmetic, Enclosures of Derivatives |
|
|
316 | |
|
9.3 The Interval Newton Method |
|
|
324 | |
|
9.4 The Extended Interval Newton Method |
|
|
327 | |
|
9.5 Verified Solution of Systems of Linear Equations |
|
|
329 | |
|
9.6 Accurate Evaluation of Arithmetic Expressions |
|
|
336 | |
|
9.6.1 Complete Expressions |
|
|
336 | |
|
9.6.2 Accurate Evaluation of Polynomials |
|
|
337 | |
|
9.6.3 Arithmetic Expressions |
|
|
341 | |
|
9.7 Multiple Precision Arithmetics |
|
|
343 | |
|
9.7.1 Multiple Precision Floating-Point Arithmetic |
|
|
344 | |
|
9.7.2 Multiple Precision Interval Arithmetic |
|
|
347 | |
|
|
|
352 | |
|
9.7.4 Adding an Exponent Part as a Scaling Factor to Complete Arithmetic |
|
|
354 | |
| A Frequently Used Symbols |
|
356 | |
| B On Homomorphism |
|
358 | |
| Bibliography |
|
359 | |
| List of Figures |
|
395 | |
| List of Tables |
|
399 | |
| Index |
|
401 | |
Rohkem infot De Gruyter e-raamatute kohta