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
arXiv:1004.4710v1
(version 0.5.1 of 27 April 2010)

or
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).

- 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 floating-point algorithms).

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 on-line documents.

Errata for earlier versions of the book are here.

- 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 speed.
- Zen, 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.

- hgcd.c
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 10
^{7}limbs, i.e, about 193 million decimal digits, in 738.5s with`mpz_gcd`and 725.1s with`mpz_bgcd`. For 10^{8}limbs, i.e., about 1.9 billion decimal digits,`mpz_gcd`takes 11776s and`mpz_bgcd`takes 11031s, thus a 6.3% speedup.

*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
[chapters 9-12].

*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,
Birkhäuser, 2009.

*Matters Computational*,
Jörg Arndt,
Springer, 2010, also
freely available online.

*Finite Precision Number Systems and Arithmetic*,
Peter Kornerup and David W. Matula,
Cambridge University Press, 2010.

See also the ``Algorithms'' chapter from the GMP reference manual.

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