Modern computer arithmetic

Contents......Page 3
Preface......Page 9
Acknowledgements......Page 11
Notation......Page 13
Representation and Notations......Page 17
Addition and Subtraction......Page 18
Multiplication......Page 19
Naive Multiplication......Page 20
Karatsuba's Algorithm......Page 21
Toom-Cook Multiplication......Page 23
Use of the Fast Fourier Transform (FFT)......Page 24
Unbalanced Multiplication......Page 25
Squaring......Page 28
Division......Page 31
Naive Division......Page 32
Divisor Preconditioning......Page 34
Divide and Conquer Division......Page 35
Newton's Method......Page 38
Exact Division......Page 39
Only Quotient or Remainder Wanted......Page 40
Division by a Single Word......Page 41
Hensel's Division......Page 42
Square Root......Page 43
k-th Root......Page 45
Exact Root......Page 46
Greatest Common Divisor......Page 47
Naive GCD......Page 48
Extended GCD......Page 51
Half Binary GCD, Divide and Conquer GCD......Page 52
Quadratic Algorithms......Page 56
Subquadratic Algorithms......Page 57
Exercises......Page 58
Notes and References......Page 63
Classical Representation......Page 67
Montgomery's Form......Page 68
Link with Polynomials......Page 69
The Fourier Transform......Page 70
Theoretical Setting......Page 71
The Fast Fourier Transform......Page 72
The Schönhage-Strassen Algorithm......Page 76
Barrett's Algorithm......Page 79
Montgomery's Multiplication......Page 81
McLaughlin's Algorithm......Page 84
Modular Division and Inversion......Page 86
Several Inversions at Once......Page 88
Modular Exponentiation......Page 90
Binary Exponentiation......Page 91
Exponentiation With a Larger Base......Page 92
Sliding Window and Redundant Representation......Page 93
Chinese Remainder Theorem......Page 95
Exercises......Page 97
Notes and References......Page 99
Representation......Page 101
Exponent Range......Page 103
Subnormal Numbers......Page 104
Encoding......Page 106
Precision: Local, Global, Operation, Operand......Page 107
Link to Integers......Page 108
Ziv's Algorithm and Error Analysis......Page 109
Rounding......Page 110
Strategies......Page 114
Floating-Point Addition......Page 115
Floating-Point Subtraction......Page 117
Multiplication......Page 119
Integer Multiplication via Complex FFT......Page 123
The Middle Product......Page 125
Reciprocal and Division......Page 126
Reciprocal......Page 127
Division......Page 131
Square Root......Page 136
Reciprocal Square Root......Page 137
Floating-Point Output......Page 140
Floating-Point Input......Page 143
Exercises......Page 144
Notes and References......Page 146
Introduction......Page 151
Newton's Method......Page 152
Newton's Method for Reciprocals......Page 154
Newton's Method for (Reciprocal) Square Roots......Page 155
Newton's Method for Formal Power Series......Page 156
Newton's Method for Functional Inverses......Page 157
Higher Order Newton-like Methods......Page 158
Argument Reduction......Page 159
Loss of Precision......Page 161
Guard Digits......Page 162
Doubling versus Tripling......Page 163
Power Series......Page 164
Power Series With Argument Reduction......Page 168
Rectangular Series Splitting......Page 169
Asymptotic Expansions......Page 173
Continued Fractions......Page 179
Recurrence Relations......Page 181
Evaluation of Bessel Functions......Page 182
Evaluation of Bernoulli and Tangent numbers......Page 183
Arithmetic-Geometric Mean......Page 187
Elliptic Integrals......Page 188
First AGM Algorithm for the Logarithm......Page 189
Theta Functions......Page 190
Second AGM Algorithm for the Logarithm......Page 191
The Complex AGM......Page 193
Binary Splitting......Page 194
A Binary Splitting Algorithm for sin, cos......Page 196
The Bit-Burst Algorithm......Page 197
Contour Integration......Page 200
Exercises......Page 201
Notes and References......Page 210
CLN......Page 217
GNU MP (GMP)......Page 218
Other Multiple-Precision Packages......Page 219
Computational Algebra Packages......Page 220
On-line Documents......Page 222
Bibliography......Page 225
Index......Page 245
Summary of Complexities......Page 261