Modern Computer Arithmetic focuses on arbitrary-precision algorithms for efficiently performing arithmetic operations such as addition, multiplication and division, and their connections to topics such as modular arithmetic, greatest common divisors, the Fast Fourier Transform (FFT), and the computation of elementary and special functions. Brent and Zimmermann present algorithms that are ready to implement in your favorite language, while keeping a high-level description and avoiding too low-level or machine-dependent details. The book is intended for anyone interested in the design and implementation of efficient high-precision algorithms for computer arithmetic, and more generally efficient multiple-precision numerical algorithms. It may also be used in a graduate course in mathematics or computer science, for which exercises are included. These vary considerably in difficulty, from easy to small research projects, and expand on topics discussed in the text. Solutions are available from the authors.
Author(s): Richard Brent, Paul Zimmermann
Publisher: Cambridge University Press
Year: 2010
Language: English
Pages: 239
Tags: Математика;Вычислительная математика;
Cover......Page 1
Title......Page 5
Copyright......Page 6
Contents......Page 7
Preface......Page 11
Acknowledgements......Page 13
Notation......Page 15
1.1 Representation and notations......Page 19
1.2 Addition and subtraction......Page 20
1.3 Multiplication......Page 21
1.3.1 Naive multiplication......Page 22
1.3.2 Karatsuba's algorithm......Page 23
1.3.3 Toom–Cook multiplication......Page 24
1.3.5 Unbalanced multiplication......Page 26
1.3.6 Squaring......Page 29
1.3.7 Multiplication by a constant......Page 31
1.4.1 Naive division......Page 32
1.4.2 Divisor preconditioning......Page 34
1.4.3 Divide and conquer division......Page 36
Unbalanced division......Page 37
1.4.5 Exact division......Page 39
1.4.6 Only quotient or remainder wanted......Page 40
1.4.7 Division by a single word......Page 41
1.4.8 Hensel's division......Page 42
1.5.1 Square root......Page 43
1.5.2 kth root......Page 45
Unknown exponent......Page 46
1.6.1 Naive GCD......Page 47
Sorenson’s k-ary reduction......Page 49
1.6.2 Extended GCD......Page 50
1.6.3 Half binary GCD, divide and conquer GCD......Page 51
1.7.1 Quadratic algorithms......Page 55
1.7.2 Subquadratic algorithms......Page 56
1.8 Exercises......Page 57
1.9 Notes and references......Page 62
2.1.1 Classical representation......Page 65
2.1.3 Residue number systems......Page 66
2.1.5 Link with polynomials......Page 67
2.3.1 Theoretical setting......Page 68
2.3.2 The fast Fourier transform......Page 69
2.3.3 The Schönhage–Strassen algorithm......Page 73
2.4.1 Barrett's algorithm......Page 76
2.4.2 Montgomery's multiplication......Page 78
Subquadratic Montgomery reduction......Page 80
2.4.3 McLaughlin's algorithm......Page 81
2.5 Modular division and inversion......Page 83
2.5.1 Several inversions at once......Page 85
2.6 Modular exponentiation......Page 86
2.6.2 Exponentiation with a larger base......Page 88
2.6.3 Sliding window and redundant representation......Page 90
2.7 Chinese remainder theorem......Page 91
2.8 Exercises......Page 93
2.9 Notes and references......Page 95
3.1 Representation......Page 97
3.1.1 Radix choice......Page 98
3.1.2 Exponent range......Page 99
3.1.4 Subnormal numbers......Page 100
3.1.5 Encoding......Page 101
3.1.6 Precision: local, global, operation, operand......Page 102
3.1.8 Ziv's algorithm and error analysis......Page 104
3.1.9 Rounding......Page 105
3.1.10 Strategies......Page 108
3.2 Addition, subtraction, comparison......Page 109
3.2.1 Floating-point addition......Page 110
3.2.2 Floating-point subtraction......Page 111
Sterbenz’s theorem......Page 112
3.3 Multiplication......Page 113
3.3.1 Integer multiplication via complex FFT......Page 116
3.3.2 The middle product......Page 117
3.4 Reciprocal and division......Page 119
3.4.1 Reciprocal......Page 120
3.4.2 Division......Page 124
Barrett’s floating-point division algorithm......Page 127
3.5 Square root......Page 129
3.5.1 Reciprocal square root......Page 130
3.6 Conversion......Page 132
3.6.1 Floating-point output......Page 133
3.6.2 Floating-point input......Page 135
3.7 Exercises......Page 136
3.8 Notes and references......Page 138
4.1 Introduction......Page 143
Newton’s method via linearization......Page 144
4.2.1 Newton's method for inverse roots......Page 145
Computational issues......Page 146
4.2.4 Newton's method for formal power series......Page 147
4.2.5 Newton's method for functional inverses......Page 148
4.2.6 Higher-order Newton-like methods......Page 149
4.3 Argument reduction......Page 150
4.3.2 Loss of precision......Page 152
4.3.3 Guard digits......Page 153
4.4 Power series......Page 154
The radius of convergence......Page 157
4.4.2 Power series with argument reduction......Page 158
4.4.3 Rectangular series splitting......Page 159
Modular splitting......Page 160
Complexity of rectangular series splitting......Page 161
4.5 Asymptotic expansions......Page 162
4.6 Continued fractions......Page 168
4.7 Recurrence relations......Page 170
4.7.1 Evaluation of Bessel functions......Page 171
4.7.2 Evaluation of Bernoulli and tangent numbers......Page 172
4.8.1 Elliptic integrals......Page 176
4.8.2 First AGM algorithm for the logarithm......Page 177
4.8.3 Theta functions......Page 178
4.8.4 Second AGM algorithm for the logarithm......Page 180
4.9 Binary splitting......Page 181
4.9.1 A binary splitting algorithm for sin, cos......Page 184
4.9.2 The bit-burst algorithm......Page 185
4.10 Contour integration......Page 187
4.11 Exercises......Page 189
4.12 Notes and references......Page 197
5.1.2 GNU MP (GMP)......Page 203
5.1.3 MPFQ......Page 204
5.1.5 Other multiple-precision packages......Page 205
5.1.6 Computational algebra packages......Page 206
5.2.1 The GMP lists......Page 207
5.3 On-line documents......Page 208
References......Page 209
Index......Page 225
