Modern Computer Arithmetic
226. R. P. Brent and
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 this topic is
Volume 2 of Knuth's The Art of Computer Programming,
which omits some new important algorithms (divide and conquer division,
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),
- including all details (for example how to properly deal with carries
for integer algorithms, and a rigorous analysis of roundoff errors for
floating-point algorithms).
The book will 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 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).
Errata
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.
Go to next publication
Return to Richard Brent's index page