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:

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: 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

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