Modern Computer Arithmetic

Contents......Page 1
Preface......Page 10
Acknowledgements......Page 12
Notation......Page 14
Representation and notations......Page 18
Addition and subtraction......Page 19
Multiplication......Page 20
Naive multiplication......Page 21
Karatsuba's algorithm......Page 22
Toom--Cook multiplication......Page 23
Unbalanced multiplication......Page 25
Squaring......Page 28
Multiplication by a constant......Page 30
Naive division......Page 31
Divisor preconditioning......Page 33
Divide and conquer division......Page 35
Exact division......Page 38
Only quotient or remainder wanted......Page 39
Division by a single word......Page 40
Hensel's division......Page 41
Square root......Page 42
kth root......Page 44
Exact root......Page 45
Naive GCD......Page 46
Extended GCD......Page 49
Half binary GCD, divide and conquer GCD......Page 50
Quadratic algorithms......Page 54
Subquadratic algorithms......Page 55
Exercises......Page 56
Notes and references......Page 61
Classical representation......Page 64
Residue number systems......Page 65
Link with polynomials......Page 66
Theoretical setting......Page 67
The fast Fourier transform......Page 68
The Schönhage--Strassen algorithm......Page 72
Barrett's algorithm......Page 75
Montgomery's multiplication......Page 77
McLaughlin's algorithm......Page 80
Modular division and inversion......Page 82
Several inversions at once......Page 84
Modular exponentiation......Page 85
Exponentiation with a larger base......Page 87
Sliding window and redundant representation......Page 89
Chinese remainder theorem......Page 90
Exercises......Page 92
Notes and references......Page 94
Representation......Page 96
Radix choice......Page 97
Exponent range......Page 98
Subnormal numbers......Page 99
Encoding......Page 100
Precision: local, global, operation, operand......Page 101
Ziv's algorithm and error analysis......Page 103
Rounding......Page 104
Strategies......Page 107
Addition, subtraction, comparison......Page 108
Floating-point addition......Page 109
Floating-point subtraction......Page 110
Multiplication......Page 112
Integer multiplication via complex FFT......Page 115
The middle product......Page 116
Reciprocal and division......Page 118
Reciprocal......Page 119
Division......Page 123
Square root......Page 128
Reciprocal square root......Page 129
Conversion......Page 131
Floating-point output......Page 132
Floating-point input......Page 134
Exercises......Page 135
Notes and references......Page 137
Introduction......Page 142
Newton's method......Page 143
Newton's method for inverse roots......Page 144
Newton's method for reciprocals......Page 145
Newton's method for formal power series......Page 146
Newton's method for functional inverses......Page 147
Higher-order Newton-like methods......Page 148
Argument reduction......Page 149
Loss of precision......Page 151
Guard digits......Page 152
Power series......Page 153
Power series with argument reduction......Page 157
Rectangular series splitting......Page 158
Asymptotic expansions......Page 161
Continued fractions......Page 167
Recurrence relations......Page 169
Evaluation of Bessel functions......Page 170
Evaluation of Bernoulli and tangent numbers......Page 171
Elliptic integrals......Page 175
First AGM algorithm for the logarithm......Page 176
Theta functions......Page 177
Second AGM algorithm for the logarithm......Page 179
Binary splitting......Page 180
A binary splitting algorithm for sin, cos......Page 183
The bit-burst algorithm......Page 184
Contour integration......Page 186
Exercises......Page 188
Notes and references......Page 196
GNU MP (GMP)......Page 202
MPFQ......Page 203
Other multiple-precision packages......Page 204
Computational algebra packages......Page 205
The GMP lists......Page 206
On-line documents......Page 207
References......Page 208
Index......Page 224