Modern Computer Arithmetic

by Richard P. Brent , Paul Zimmermann

• ISBN13: 9780521194693
• ISBN10: 0521194695
• Format: Hardcover
• Copyright: 2010-12-27
• Publisher: Cambridge University Press

Summary

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 favourite 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 Biography

Richard Brent is a Professor of Mathematics and Computer Science at the Australian National University, Canberra. Paul Zimmermann is a Researcher at the Institut National de Recherche en Informatique et en Automatique (INRIA), France.

Table of Contents

Preface	p. ix
Acknowledgements	p. xi
Notation	p. xiii
Integer arithmetic	p. 1
Representation and notations	p. 1
Addition and subtraction	p. 2
Multiplication	p. 3
Naive multiplication	p. 4
Karatsuba's algorithm	p. 5
Toom-Cook multiplication	p. 6
Use of the fast Fourier transform (FFT)	p. 8
Unbalanced multiplication	p. 8
Squaring	p. 11
Multiplication by a constant	p. 13
Division	p. 14
Naive division	p. 14
Divisor preconditioning	p. 16
Divide and conquer division	p. 18
Newton's method	p. 21
Exact division	p. 21
Only quotient or remainder wanted	p. 22
Division by a single word	p. 23
Hensel's division	p. 24
Roots	p. 25
Square root	p. 25
kth root	p. 27
Exact root	p. 28
Greatest common divisor	p. 29
Naive GCD	p. 29
Extended GCD	p. 32
Half binary GCD, divide and conquer GCD	p. 33
Base conversion	p. 37
Quadratic algorithms	p. 37
Subquadratic algorithms	p. 38
Exercises	p. 39
Notes and references	p. 44
Modular arithmetic and the FFT	p. 47
Representation	p. 47
Classical representation	p. 47
Montgomery's form	p. 48
Residue number systems	p. 48
MSB vs LSB algorithms	p. 49
Link with polynomials	p. 49
Modular addition and subtraction	p. 50
The Fourier transform	p. 50
Theoretical setting	p. 50
The fast Fourier transform	p. 51
The Schönhage-Strassen algorithm	p. 55
Modular multiplication	p. 58
Barrett's algorithm	p. 58
Montgomery's multiplication	p. 60
McLaughlin's algorithm	p. 63
Special moduli	p. 65
Modular division and inversion	p. 65
Several inversions at once	p. 67
Modular exponentiation	p. 68
Binary exponentiation	p. 70
Exponentiation with a larger base	p. 70
Sliding window and redundant representation	p. 72
Chinese remainder theorem	p. 73
Exercises	p. 75
Notes and references	p. 77
Floating-point arithmetic	p. 79
Representation	p. 79
Radix choice	p. 80
Exponent range	p. 81
Special values	p. 82
Subnormal numbers	p. 82
Encoding	p. 83
Precision: local, global, operation, operand	p. 84
Link to integers	p. 86
Ziv's algorithm and error analysis	p. 86
Rounding	p. 87
Strategies	p. 90
Addition, subtraction, comparison	p. 91
Floating-point addition	p. 92
Floating-point subtraction	p. 93
Multiplication	p. 95
Integer multiplication via complex FFT	p. 98
The middle product	p. 99
Reciprocal and division	p. 101
Reciprocal	p. 102
Division	p. 106
Square root	p. 111
Reciprocal square root	p. 112
Conversion	p. 114
Floating-point output	p. 115
Floating-point input	p. 117
Exercises	p. 118
Notes and references	p. 120
Elementary and special function evaluation	p. 125
Introduction	p. 125
Newton's method	p. 126
Newton's method for inverse roots	p. 127
Newton's method for reciprocals	p. 128
Newton's method for (reciprocal) square roots	p. 129
Newton's method for formal power series	p. 129
Newton's method for functional inverses	p. 130
Higher-order Newton-like methods	p. 131
Argument reduction	p. 132
Repeated use of a doubling formula	p. 134
Loss of precision	p. 134
Guard digits	p. 135
Doubling versus tripling	p. 136
Power series	p. 136
Direct power series evaluation	p. 140
Power series with argument reduction	p. 140
Rectangular series splitting	p. 141
Asymptotic expansions	p. 144
Continued fractions	p. 150
Recurrence relations	p. 152
Evaluation of Bessel functions	p. 153
Evaluation of Bernoulli and tangent numbers	p. 154
Arithmetic-geometric mean	p. 158
Elliptic integrals	p. 158
First AGM algorithm for the logarithm	p. 159
Theta functions	p. 160
Second AGM algorithm for the logarithm	p. 162
The complex AGM	p. 163
Binary splitting	p. 163
A binary splitting algorithm for sin, cos	p. 166
The bit-burst algorithm	p. 167
Contour integration	p. 169
Exercises	p. 171
Notes and references	p. 179
Implementations and pointers	p. 185
Software tools	p. 185
CLN	p. 185
GNU MP(GMP)	p. 185
MPFQ	p. 186
GNU MPFR	p. 187
Other multiple-precision packages	p. 187
Computational algebra packages	p. 188
Mailing lists	p. 189
The GMP lists	p. 189
The MPFR list	p. 190
On-line documents	p. 190
References	p. 191
Index	p. 207
Table of Contents provided by Ingram. All Rights Reserved.