Modern Computer Arithmetic

R. P. Brent, P. Zimmermann, Modern Computer Arithmetic, Cambridge Monographs on Computational and Applied Mathematics (No. 18), Cambridge University Press, November 2010, 236 pages. Publisher's web page.

To cite this document, please use the following:

Preliminary versions of the book are available here:

Version 0.5.9 (October 2010), xvi+223 pages; this version corresponds quite closely to the version published by Cambridge University Press (the only differences being that pages i-viii slightly differ, and the three typos reported by Torbjörn Granlund on version 0.5.7 are fixed in 0.5.9).

Previous versions: Version 0.5.7 (September 2010), xvi+223 pages, Version 0.5.5 (September 2010), xvi+223 pages, Version 0.5.3 (August 2010), xvi+223 pages, Version 0.5.1 (March 2010), xvi+227 pages, Version 0.5 (February 2010), xvi+245 pages, Version 0.4 (November 2009), 239 pages, Version 0.3 (June 2009), 221 pages, Version 0.2.1 (March 2009), 215 pages, Version 0.2 (June 2008), 190 pages, Version 0.1.1 (November 2006), 94 pages, Version 0.1 (October 2006), 91 pages. For the electronic versions, copying this work is allowed for non-commercial use (see the license on page iii of the pdf file).

Abstract

This is a book about algorithms for performing arithmetic, and their implementation on modern computers. It collects in the same document all state-of-the-art algorithms in multiple precision arithmetic (integers, integers modulo n, floating-point numbers). The best current reference on that topic is volume 2 from Knuth's The art of computer programming, which misses some new important algorithms (divide and conquer division, other variants of FFT multiplication, floating-point algorithms, ...) Our aim is to give detailed algorithms: The book is useful for graduate students in computer science and mathematics (perhaps too specialized for most undergraduates, at least in its present state), researchers in discrete mathematics, computer algebra, number theory, cryptography, and developers of multiple-precision libraries.

Summary

Chapter 1 describes integer arithmetic (representation, addition, subtraction, multiplication, division, roots, gcd, base conversion).
Chapter 2 deals with modular arithmetic (representation, multiplication, division/inversion, exponentiation, conversion, applications of FFT).
Chapter 3 treats with floating-point arithmetic (addition, subtraction, comparison, multiplication, division, algebraic functions, conversion).
Chapter 4 covers Newton's method and function evaluation (Newton's method and its variants, argument reduction, power series, asymptotic expansions, continued fractions, recurrence relations, arithmetic-geometric mean, binary splitting, D-finite functions, contour integration, constants).
Finally, an appendix gives pointers to software tools, mailing-lists, and on-line documents.

Exercises

The book contains many exercises, which vary considerably in difficulty. Here are solutions to selected exercises.

Errata

Errata for the printed (CUP) version of the book and electronic versions 0.5.7 and later may be found here.

Errata for earlier versions of the book are here.

Software

Many algorithms from the book are implemented in the GNU MP and MPFR libraries. Other relevant packages are: The following programs illustrate algorithms from the book:

Books on Related Topics

The Art of Computer Programming, volume 2: Seminumerical Algorithms, Donald E. Knuth, 3rd edition, 1998.

Modern Computer Algebra , Joachim von zur Gathen and Jürgen Gerhard, Cambridge University Press, 2nd edition, 2003.

The Design and Analysis of Computer Algorithms, A. V. Aho, J. E. Hopcroft and J. D. Ullman, Addison-Wesley, 1974 [chapters 7 and 8].

The Computational Complexity of Algebraic and Numeric Problems, A. Borodin and I. Munro, Elsevier Computer Science Library, 1975.

Handbook of Applied Cryptography, Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, CRC Press, 1997 [chapter 14].

Prime Numbers: A Computational Perspective, Richard E. Crandall and Carl Pomerance, Springer Verlag, 2001 [chapter 9].

Fast Algorithms, A Multitape Turing Machine Implementation, Arnold Schönhage and A. F. W. Grotefeld and E. Vetter, BI-Wissenschaftsverlag, 1994 [out of print].

Handbook of Elliptic and Hyperelliptic Curve Cryptography, Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, Frederik Vercauteren, Chapman & Hall/CRC, series Discrete Mathematics and its Applications, 2005 [chapters 9-12].

Handbook of Floating-Point Arithmetic, Nicolas Brisebarre, Florent de Dinechin, Claude-Pierre Jeannerod, Vincent Lefèvre, Guillaume Melquiond, Jean-Michel Muller, Nathalie Revol, Damien Stehlé and Serge Torres, Birkhäuser, 2009.

Matters Computational, Jörg Arndt, Springer, 2010, also freely available online.

See also the ``Algorithms'' chapter from the GMP reference manual.

Reviews

For a review of the book by Warren Ferguson, see SIAM Review, 53, 4 (December 2011), 809-810.

Citations

The FEE method of E. A. Karatsuba

The reader may wonder why our book does not refer to the FEE method of E. A. Karatsuba. In fact, various drafts of Chapter 4 of the book did refer to this method, but our publisher (CUP) asked us to remove such references to avoid any possibility of legal problems. For brief comments on the FEE method, see for example the draft of the book that is available at arXiv:1004.4710.