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