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
k-th Root......Page 43
Exact Root......Page 44
Naive GCD......Page 45
Extended GCD......Page 48
Half Binary GCD, Divide and Conquer GCD......Page 49
Quadratic Algorithms......Page 53
Subquadratic Algorithms......Page 54
Exercises......Page 55
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 80
Modular Division and Inversion......Page 81
Several Inversions at Once......Page 83
Modular Exponentiation......Page 84
Binary Exponentiation......Page 86
Exponentiation With a Larger Base......Page 87
Sliding Window and Redundant Representation......Page 88
Chinese Remainder Theorem......Page 89
Exercises......Page 91
Notes and References......Page 93
Representation......Page 97
Radix Choice......Page 98
Exponent Range......Page 99
Subnormal Numbers......Page 100
Encoding......Page 101
Precision: Local, Global, Operation, Operand......Page 102
Link to Integers......Page 103
Ziv's Algorithm and Error Analysis......Page 104
Rounding......Page 105
Addition, Subtraction, Comparison......Page 109
Floating-Point Addition......Page 110
Floating-Point Subtraction......Page 112
Multiplication......Page 113
Integer Multiplication via Complex FFT......Page 117
The Middle Product......Page 118
Reciprocal......Page 120
Division......Page 124
Square Root......Page 129
Reciprocal Square Root......Page 130
Floating-Point Output......Page 133
Exercises......Page 136
Notes and References......Page 138
Introduction......Page 143
Newton's Method......Page 144
Newton's Method for Inverse Roots......Page 145
Newton's Method for Reciprocals......Page 146
Newton's Method for Formal Power Series......Page 147
Newton's Method for Functional Inverses......Page 148
Higher Order Newton-like Methods......Page 149
Argument Reduction......Page 150
Loss of Precision......Page 152
Guard Digits......Page 153
Power Series......Page 154
Power Series With Argument Reduction......Page 158
Rectangular Series Splitting......Page 159
Asymptotic Expansions......Page 162
Continued Fractions......Page 168
Recurrence Relations......Page 170
Evaluation of Bessel Functions......Page 171
Evaluation of Bernoulli and Tangent numbers......Page 172
Elliptic Integrals......Page 176
First AGM Algorithm for the Logarithm......Page 177
Theta Functions......Page 178
Second AGM Algorithm for the Logarithm......Page 180
The Complex AGM......Page 181
Binary Splitting......Page 182
A Binary Splitting Algorithm for sin, cos......Page 184
The Bit-Burst Algorithm......Page 185
Contour Integration......Page 187
Exercises......Page 189
Notes and References......Page 197
GNU MP (GMP)......Page 203
MPFQ......Page 204
Other Multiple-Precision Packages......Page 205
Computational Algebra Packages......Page 206
The BNIS Mailing List......Page 207
On-line Documents......Page 208
Bibliography......Page 211
Index......Page 227
Summary of Complexities......Page 243