Elementary Functions : Algorithms and Implementation

Contents......Page 4
List of Figures......Page 9
List of Tables......Page 12
Preface to the Second Edition......Page 16
Preface to the First Edition......Page 18
1 Introduction......Page 20
2.1.1 Floating-point formats......Page 27
2.1.2 Rounding modes......Page 29
2.1.3 Subnormal numbers and exceptions......Page 31
2.1.4 ULPs......Page 32
2.1.5 Fused multiply-add operations......Page 33
2.1.6 Testing your computational environment......Page 34
2.1.8 Maple programs that compute double-precision approximations......Page 35
2.2.1 Signed-digit number systems......Page 37
2.2.2 Radix-2 redundant number systems......Page 39
I: Algorithms Based on Polynomial Approximation and/or Table Lookup, Multiple-Precision Evaluation of Functions......Page 43
3 Polynomial or Rational Approximations......Page 44
3.1 Least Squares Polynomial Approximations......Page 45
3.2 Least Maximum Polynomial Approximations......Page 49
3.3 Some Examples......Page 50
3.4 Speed of Convergence......Page 56
3.5 Remez's Algorithm......Page 58
3.6 Rational Approximations......Page 63
3.7 Actual Computation of Approximations......Page 67
3.8 Algorithms and Architectures for the Evaluation of Polynomials......Page 71
3.9 Evaluation Error Assuming Horner's Scheme is Used......Page 76
3.10 Miscellaneous......Page 83
4.1 Introduction......Page 84
4.2 Table-Driven Algorithms......Page 87
4.3 Gal's Accurate Tables Method......Page 90
4.4 Table Methods Requiring Specialized Hardware......Page 94
5.1 Introduction......Page 105
5.2 Just a Few Words on Multiple-Precision Multiplication......Page 106
5.3 Multiple-Precision Division and Square-Root......Page 108
5.4 Algorithms Based on the Evaluation of Power Series......Page 110
5.5 The Arithmetic-Geometric (AGM) Mean......Page 111
II: Shift-and-Add Algorithms......Page 117
6 Introduction to Shift-and-Add Algorithms......Page 118
6.1 The Restoring and Nonrestoring Algorithms......Page 120
6.2 Simple Algorithms for Exponentials and Logarithms......Page 124
6.3 Faster Shift-and-Add Algorithms......Page 128
6.4 Baker's Predictive Algorithm......Page 137
6.5 Bibliographic Notes......Page 146
7.1 Introduction......Page 147
7.2 The Conventional CORDIC Iteration......Page 148
7.3 Scale Factor Compensation......Page 153
7.4 CORDIC With Redundant Number Systems and a Variable Factor......Page 155
7.5 The Double Rotation Method......Page 158
7.6 The Branching CORDIC Algorithm......Page 160
7.7 The Differential CORDIC Algorithm......Page 164
7.8 Computation of cos[sup(–1)] and sin[sup(–1)] Using CORDIC......Page 167
7.9 Variations on CORDIC......Page 170
8.1 High-Radix Algorithms......Page 171
8.2 The BKM Algorithm......Page 176
III: Range Reduction, Final Rounding and Exceptions......Page 184
9.1 Introduction......Page 185
9.2 Cody and Waite's Method for Range Reduction......Page 189
9.3 Finding Worst Cases for Range Reduction?......Page 191
9.4 The Payne and Hanek Reduction Algorithm......Page 196
9.5 The Modular Range Reduction Algorithm......Page 199
9.6 Alternate Methods......Page 203
10.1 Introduction......Page 204
10.2 Monotonicity......Page 205
10.3 Correct Rounding: Presentation of the Problem......Page 206
10.5 A "Probabilistic" Approach to the Problem......Page 209
10.6 Upper Bounds on m......Page 213
10.7 Obtained Worst Cases for Double-Precision......Page 214
11.1 Exceptions......Page 228
11.2 Notes on x[sup(y)]......Page 231
11.3 Special Functions, Functions of Complex Numbers......Page 233
12.1 Example 1: The Cyrix FastMath Processor......Page 235
12.2 The INTEL Functions Designed for the Itanium Processor......Page 236
12.4 The CRLIBM Library......Page 239
12.6 The HP-UX Compiler for the Itanium Processor......Page 241
Bibliography......Page 243
D......Page 270
K......Page 271
P......Page 272
T......Page 273
Z......Page 274