Modern computer arithmetic

Select an Action

Place Hold(s)
Add to My Lists
Email
Print

Title:

Personal Author:

Brent, Richard P.

Series:

Cambridge monographs on applied and computational mathematics ; 18

Publication Information:

Cambridge ; New York : Cambridge University Press, 2010

Physical Description:

xvi, 221 p. : ill. ; 24 cm.

ISBN:

9780521194693

Subject Term:

Computer arithmetic

Added Author:

Zimmermann, Paul, 1964-

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010251414	QA76.9.C62 B74 2011	Open Access Book	Book	Searching... Unknown

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 Notes

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.

Preface	p. ix
Acknowledgements	p. xi
Notation	p. xiii
1 Integer arithmetic	p. 1
1.1 Representation and notations	p. 1
1.2 Addition and subtraction	p. 2
1.3 Multiplication	p. 3
1.3.1 Naive multiplication	p. 4
1.3.2 Karatsuba's algorithm	p. 5
1.3.3 Toom-Cook multiplication	p. 6
1.3.4 Use of the fast Fourier transform (FFT)	p. 8
1.3.5 Unbalanced multiplication	p. 8
1.3.6 Squaring	p. 11
1.3.7 Multiplication by a constant	p. 13
1.4 Division	p. 14
1.4.1 Naive division	p. 14
1.4.2 Divisor preconditioning	p. 16
1.4.3 Divide and conquer division	p. 18
1.4.4 Newton's method	p. 21
1.4.5 Exact division	p. 21
1.4.6 Only quotient or remainder wanted	p. 22
1.4.7 Division by a single word	p. 23
1.4.8 Hensel's division	p. 24
1.5 Roots	p. 25
1.5.1 Square root	p. 25
1.5.2 kth root	p. 27
1.5.3 Exact root	p. 28
1.6 Greatest common divisor	p. 29
1.6.1 Naive GCD	p. 29
1.6.2 Extended GCD	p. 32
1.6.3 Half binary GCD, divide and conquer GCD	p. 33
1.7 Base conversion	p. 37
1.7.1 Quadratic algorithms	p. 37
1.7.2 Subquadratic algorithms	p. 38
1.8 Exercises	p. 39
1.9 Notes and references	p. 44
2 Modular arithmetic and the FFT	p. 47
2.1 Representation	p. 47
2.1.1 Classical representation	p. 47
2.1.2 Montgomery's form	p. 48
2.1.3 Residue number systems	p. 48
2.1.4 MSB vs LSB algorithms	p. 49
2.1.5 Link with polynomials	p. 49
2.2 Modular addition and subtraction	p. 50
2.3 The Fourier transform	p. 50
2.3.1 Theoretical setting	p. 50
2.3.2 The fast Fourier transform	p. 51
2.3.3 The Schönhage-Strassen algorithm	p. 55
2.4 Modular multiplication	p. 58
2.4.1 Barrett's algorithm	p. 58
2.4.2 Montgomery's multiplication	p. 60
2.4.3 McLaughlin's algorithm	p. 63
2.4.4 Special moduli	p. 65
2.5 Modular division and inversion	p. 65
2.5.1 Several inversions at once	p. 67
2.6 Modular exponentiation	p. 68
2.6.1 Binary exponentiation	p. 70
2.6.2 Exponentiation with a larger base	p. 70
2.6.3 Sliding window and redundant representation	p. 72
2.7 Chinese remainder theorem	p. 73
2.8 Exercises	p. 75
2.9 Notes and references	p. 77
3 Floating-point arithmetic	p. 79
3.1 Representation	p. 79
3.1.1 Radix choice	p. 80
3.1.2 Exponent range	p. 81
3.1.3 Special values	p. 82
3.1.4 Subnormal numbers	p. 82
3.1.5 Encoding	p. 83
3.1.6 Precision: local, global, operation, operand	p. 84
3.1.7 Link to integers	p. 86
3.1.8 Ziv's algorithm and error analysis	p. 86
3.1.9 Rounding	p. 87
3.1.10 Strategies	p. 90
3.2 Addition, subtraction, comparison	p. 91
3.2.1 Floating-point addition	p. 92
3.2.2 Floating-point subtraction	p. 93
3.3 Multiplication	p. 95
3.3.1 Integer multiplication via complex FFT	p. 98
3.3.2 The middle product	p. 99
3.4 Reciprocal and division	p. 101
3.4.1 Reciprocal	p. 102
3.4.2 Division	p. 106
3.5 Square root	p. 111
3.5.1 Reciprocal square root	p. 112
3.6 Conversion	p. 114
3.6.1 Floating-point output	p. 115
3.6.2 Floating-point input	p. 117
3.7 Exercises	p. 118
3.8 Notes and references	p. 120
4 Elementary and special function evaluation	p. 125
4.1 Introduction	p. 125
4.2 Newton's method	p. 126
4.2.1 Newton's method for inverse roots	p. 127
4.2.2 Newton's method for reciprocals	p. 128
4.2.3 Newton's method for (reciprocal) square roots	p. 129
4.2.4 Newton's method for formal power series	p. 129
4.2.5 Newton's method for functional inverses	p. 130
4.2.6 Higher-order Newton-like methods	p. 131
4.3 Argument reduction	p. 132
4.3.1 Repeated use of a doubling formula	p. 134
4.3.2 Loss of precision	p. 134
4.3.3 Guard digits	p. 135
4.3.4 Doubling versus tripling	p. 136
4.4 Power series	p. 136
4.4.1 Direct power series evaluation	p. 140
4.4.2 Power series with argument reduction	p. 140
4.4.3 Rectangular series splitting	p. 141
4.5 Asymptotic expansions	p. 144
4.6 Continued fractions	p. 150
4.7 Recurrence relations	p. 152
4.7.1 Evaluation of Bessel functions	p. 153
4.7.2 Evaluation of Bernoulli and tangent numbers	p. 154
4.8 Arithmetic-geometric mean	p. 158
4.8.1 Elliptic integrals	p. 158
4.8.2 First AGM algorithm for the logarithm	p. 159
4.8.3 Theta functions	p. 160
4.8.4 Second AGM algorithm for the logarithm	p. 162
4.8.5 The complex AGM	p. 163
4.9 Binary splitting	p. 163
4.9.1 A binary splitting algorithm for sin, cos	p. 166
4.9.2 The bit-burst algorithm	p. 167
4.10 Contour integration	p. 169
4.11 Exercises	p. 171
4.12 Notes and references	p. 179
5 Implementations and pointers	p. 185
5.1 Software tools	p. 185
5.1.1 CLN	p. 185
5.1.2 GNU MP(GMP)	p. 185
5.1.3 MPFQ	p. 186
5.1.4 GNU MPFR	p. 187
5.1.5 Other multiple-precision packages	p. 187
5.1.6 Computational algebra packages	p. 188
5.2 Mailing lists	p. 189
5.2.1 The GMP lists	p. 189
5.2.2 The MPFR list	p. 190
5.3 On-line documents	p. 190
References	p. 191
Index	p. 207

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents