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