Modern Computer Arithmetic
226. R. P. Brent and
Modern Computer Arithmetic,
Cambridge Monographs on Computational and Applied Mathematics
Cambridge University Press,
November 2010, 236 pages.
Publisher's web page.
A preliminary (electronic) version of the book is available here:
Version 0.5.9 (7 October 2010),
xvi+223 pages (2.0 MB).
Versions with larger (12pt) fonts are available from
(version 0.5.1 of 27 April 2010)
here (version 0.5.2 of 31 July 2010).
For other versions, see
Paul Zimmermann's page.
For the electronic versions, copying this work is allowed for non-commercial
use (see the license on page iii of the pdf file).
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 for 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,
other variants of FFT multiplication, floating-point algorithms, ...).
Our aim is to give detailed algorithms:
The book should be useful for graduate students in computer science and
mathematics (perhaps too specialized for most undergraduates),
researchers in discrete mathematics, computer
algebra, number theory, cryptography, and developers of multiple-precision
- for all operations (not just multiplication as in 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 (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, Chapter 5 gives pointers to software tools, mailing-lists, and
The book contains many exercises, which vary considerably in difficulty.
For solutions to selected exercises, please contact one of the authors.
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
Many algorithms from the book are implemented in the
GNU MP and
Other relevant packages are:
The following programs illustrate algorithms from the book:
- fastfunlib is a C
library for fast multiprecision evaluation of transcendental functions,
using fixed-point arithmetic directly on top of GMP/MPIR. The goal is
to provide optimized base implementations of transcendental functions,
with minimal overhead at low precision as well as asymptotic
from Reynald Lercier and Florent Chabaud, which provides
fast arithmetic in polynomial finite rings over Z/nZ, with application
to integer factorization and primality testing.
is an implementation of the binary (or 2-adic or LSB or right-to-left)
subquadratic gcd of Stehlé and Zimmermann. It is quite efficient
compared to the code in GMP 4.3.1 (which implements the classical
MSB or left-to-right reduction). For example on a Core 2 at 2.83Ghz
we can compute the GCD of two numbers of 107 limbs, i.e,
about 193 million decimal digits, in 738.5s with mpz_gcd and
725.1s with mpz_bgcd. For 108 limbs, i.e., about
1.9 billion decimal digits, mpz_gcd takes 11776s and
mpz_bgcd takes 11031s, thus a 6.3% speedup.
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. 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
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,
Springer, 2010, also
freely available online.
See also the ``Algorithms'' chapter from the
GMP reference manual.
For a review of the book by Warren Ferguson, see SIAM Review,
53, 4 (December 2011), 809-810.
- 31 December 2009:
Fabrice Bellard set a new record for computing digits of Pi, with
2700 billion digits,
and referrred to our book when describing the algorithms used
to obtain this record.
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
Go to next publication
Return to Richard Brent's index page