Modern computer arithmetic

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 22 Unbalanced multiplication......Page 24 Squaring......Page 27 Multiplication by a constant......Page 29 Naive division......Page 30 Divisor preconditioning......Page 32 Divide and conquer division......Page 34 Exact division......Page 37 Only quotient or remainder wanted......Page 38 Division by a single word......Page 39 Hensel's division......Page 40 Square root......Page 41 kth root......Page 43 Exact root......Page 44 Naive GCD......Page 45 Extended GCD......Page 48 Half binary GCD, divide and conquer GCD......Page 49 Base conversion......Page 53 Subquadratic algorithms......Page 54 Exercises......Page 56 Notes and references......Page 60 Classical representation......Page 63 Residue number systems......Page 64 Link with polynomials......Page 65 Theoretical setting......Page 66 The fast Fourier transform......Page 67 The Schönhage--Strassen algorithm......Page 71 Barrett's algorithm......Page 74 Montgomery's multiplication......Page 76 McLaughlin's algorithm......Page 79 Modular division and inversion......Page 81 Several inversions at once......Page 83 Modular exponentiation......Page 84 Exponentiation with a larger base......Page 86 Sliding window and redundant representation......Page 88 Chinese remainder theorem......Page 89 Exercises......Page 91 Notes and references......Page 93 Representation......Page 95 Radix choice......Page 96 Exponent range......Page 97 Subnormal numbers......Page 98 Encoding......Page 99 Precision: local, global, operation, operand......Page 100 Ziv's algorithm and error analysis......Page 102 Rounding......Page 103 Strategies......Page 106 Addition, subtraction, comparison......Page 107 Floating-point addition......Page 108 Floating-point subtraction......Page 109 Multiplication......Page 111 Integer multiplication via complex FFT......Page 114 The middle product......Page 115 Reciprocal and division......Page 117 Reciprocal......Page 118 Division......Page 122 Square root......Page 127 Reciprocal square root......Page 128 Conversion......Page 130 Floating-point output......Page 131 Floating-point input......Page 133 Exercises......Page 134 Notes and references......Page 136 Introduction......Page 141 Newton's method......Page 142 Newton's method for inverse roots......Page 143 Newton's method for reciprocals......Page 144 Newton's method for formal power series......Page 145 Newton's method for functional inverses......Page 146 Higher order Newton-like methods......Page 147 Argument reduction......Page 148 Loss of precision......Page 150 Guard digits......Page 151 Power series......Page 152 Power series with argument reduction......Page 156 Rectangular series splitting......Page 157 Asymptotic expansions......Page 160 Continued fractions......Page 166 Recurrence relations......Page 168 Evaluation of Bessel functions......Page 169 Evaluation of Bernoulli and tangent numbers......Page 170 Elliptic integrals......Page 174 First AGM algorithm for the logarithm......Page 175 Theta functions......Page 176 Second AGM algorithm for the logarithm......Page 178 Binary splitting......Page 179 A binary splitting algorithm for sin, cos......Page 182 The bit-burst algorithm......Page 183 Contour integration......Page 185 Exercises......Page 187 Notes and references......Page 195 GNU MP (GMP)......Page 201 MPFQ......Page 202 Other multiple-precision packages......Page 203 Computational algebra packages......Page 204 The GMP lists......Page 205 On-line documents......Page 206 References......Page 207 Index......Page 223 Summary of complexities......Page 239