E-Book Overview
Modern Computer Arithmetic focuses on arbitrary-precision algorithms for efficiently performing arithmetic operations such as addition, multiplication and division, and their connections to topics such as modular arithmetic, greatest common divisors, the Fast Fourier Transform (FFT), and the computation of elementary and special functions. Brent and Zimmermann present algorithms that are ready to implement in your favorite language, while keeping a high-level description and avoiding too low-level or machine-dependent details. The book is intended for anyone interested in the design and implementation of efficient high-precision algorithms for computer arithmetic, and more generally efficient multiple-precision numerical algorithms. It may also be used in a graduate course in mathematics or computer science, for which exercises are included. These vary considerably in difficulty, from easy to small research projects, and expand on topics discussed in the text. Solutions are available from the authors.
E-Book Content
This page intentionally left blank
CAMBRIDGE MONOGRAPHS ON APPLIED AND COMPUTATIONAL MATHEMATICS Series Editors M. ABLOWITZ, S. DAVIS, J. HINCH, A. ISERLES, J. OCKENDON, P. OLVER
18
Modern Computer Arithmetic
The Cambridge Monographs on Applied and Computational Mathematics series reflects the crucial role of mathematical and computational techniques in contemporary science. The series publishes expositions on all aspects of applicable and numerical mathematics, with an emphasis on new developments in this fast-moving area of research. State-of-the-art methods and algorithms as well as modern mathematical descriptions of physical and mechanical ideas are presented in a manner suited to graduate research students and professionals alike. Sound pedagogical presentation is a prerequisite. It is intended that books in the series will serve to inform a new generation of researchers.
A complete list of books in the series can be found at http://www.cambridge.org/uk/series/sSeries.asp?code=MACM Recent titles include the following: 6. The theory of composites, Graeme W. Milton 7. Geometry and topology for mesh generation, Herbert Edelsbrunner 8. Schwarz–Christoffel mapping, Tobin A. Driscoll & Lloyd N. Trefethen 9. High-order methods for incompressible fluid flow, M. O. Deville, P. F. Fischer & E. H. Mund 10. Practical extrapolation methods, Avram Sidi 11. Generalized Riemann problems in computational fluid dynamics, Matania Ben-Artzi & Joseph Falcovitz 12. Radial basis functions, Martin D. Buhmann 13. Iterative Krylov methods for large linear systems, Henk van der Vorst 14. Simulating Hamiltonian dynamics, Benedict Leimkuhler & Sebastian Reich 15. Collocation methods for Volterra integral and related functional differential equations, Hermann Brunner 16. Topology for computing, Afra J. Zomorodian 17. Scattered data approximation, Holger Wendland 18. Modern computer arithmetic, Richard P. Brent & Paul Zimmermann 19. Matrix preconditioning techniques and applications, Ke Chen 21. Spectral methods for time-dependent problems, Jan Hesthaven, Sigal Gottlieb & David Gottlieb 22. The mathematical foundations of mixing, Rob Sturman, Julio M. Ottino & Stephen Wiggins 23. Curve and surface reconstruction, Tamal K. Dey 24. Learning theory, Felipe Cucker & Ding Xuan Zhou 25. Algebraic geometry and statistical learning theory, Sumio Watanabe 26. A practical guide to the invariant calculus, Elizabeth Louise Mansfield
Modern Computer Arithmetic RICHARD P. BRENT Australian National University, Canberra PAUL ZIMMERMANN INRIA, Nancy
CAMBRIDGE UNIVERSITY PRESS
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, S˜ao Paulo, Delhi, Dubai, Tokyo, Mexico City Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK Published in the United States of Ame