Modern Computer Arithmetic
226. R. P. Brent,
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 (25 October 2006), 91 pages. To cite this
document, please use the following:
Modern Computer Arithmetic, Richard Brent and Paul Zimmermann,
version 0.1, October 2006, http://www.loria.fr/~zimmerma/mca/mca-0.1.pdf.
Copyright is kept by the authors before the commercial publication;
copying this work is allowed for non-commercial use.
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:
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
- 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
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.
Many algorithms from the book are implemented in the
GNU MP and
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
See also the ``Algorithms'' chapter from the
GMP reference manual,
and the Algorithms for programmers
book in progress by Jörg Arndt.