Modern Computer Arithmetic

226. R. P. Brent, P. Zimmermann, Modern Computer Arithmetic, in preparation.

Preliminary versions of the book will be published here before a commercial publication (and hopefully after if we find a commercial publisher who agrees):

Version 0.1.1 (10 November 2006), 94 pages. To cite this document, please use the following:

Modern Computer Arithmetic, Richard Brent and Paul Zimmermann, version 0.1.1, November 2006, http://www.loria.fr/~zimmerma/mca/mca-0.1.1.pdf.
Copyright is kept by the authors before the commercial publication; copying this work is allowed for non-commercial use.

Abstract

This book 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:
• for all operations (not just multiplication as many text books),
• for all size ranges (not just schoolbook methods or FFT-based methods),
• and including all details (for example how to properly deal with carries for integer algorithms, or a rigorous analysis of roundoff errors for floating-point algorithms).
The book would be 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 and finite fields (representation, multiplication, division/inversion, exponentiation, conversion, finite fields, 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, holonomic functions, contour integration, constants).

None so far.

Software

Many algorithms from the book are implemented in the GNU MP and MPFR libraries.

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].

See also the ``Algorithms'' chapter from the GMP reference manual, and the Algorithms for programmers book in progress by Jörg Arndt.