Modern Computer Arithmetic
Open accessThe DOI matches its Crossref record; 104 of the 104 references it cites were found in a registry or an index.
Abstract
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 favourite 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 to selected exercises are available from the authors.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1972) · Cited by 17,806
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,337
Handbook of applied cryptography
(1997) · Choice Reviews Online · doi:10.5860/choice.34-4512 · Cited by 10,357
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
A Treatise on the Theory of Bessel Functions.
Porter, M. B., & Watson, G. N. (1923) · The American Mathematical Monthly · doi:10.2307/2300274 · Cited by 9,380
Computer Architecture: A Quantitative Approach
Hennessy, J. L., & Patterson, D. A. (1989) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 9,375
Whittaker, E. T., & Watson, G. N. (2021) · Cambridge University Press eBooks · doi:10.1017/9781009004091 · Cited by 6,850
The algebraic eigenvalue problem
Wilkinson, J. H. (1965) · Cited by 5,833
The Algebraic Eigenvalue Problem
I., E., & Wilkinson, J. H. (1966) · Mathematics of Computation · doi:10.2307/2003558 · Cited by 5,140
The Art of Computer Programming. Volume 2: Seminumerical Algorithms.
Taussky, O., & Knuth, D. E. (1970) · The American Mathematical Monthly · doi:10.2307/2317055 · Cited by 3,822
Accuracy and Stability of Numerical Algorithms: Second Edition
Higham, N. J. (2002) · doi:10.1137/1.9780898718027 · Cited by 3,803
Asymptotics and Special Functions
Olver, F. (1997) · A K Peters/CRC Press eBooks · doi:10.1201/9781439864548 · Cited by 3,269
The On-Line Encyclopedia of Integer Sequences
Sloane, N. J. A. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-73086-6_12 · Cited by 3,225
Guide to Elliptic Curve Cryptography
(2004) · Springer Professional Computing · doi:10.1007/b97644 · Cited by 3,054
Algorithms for Minimization Without Derivatives
G., D., & Brent, R. P. (1974) · Mathematics of Computation · doi:10.2307/2005713 · Cited by 2,847
Self-citationModular multiplication without trial division
Montgomery, P. L. (1985) · Mathematics of Computation · doi:10.1090/s0025-5718-1985-0777282-x · Cited by 2,669
A Course in Computational Algebraic Number Theory
Cohen, H. (1993) · Graduate Texts in Mathematics · doi:10.1007/978-3-662-02945-9 · Cited by 2,567
Concrete Mathematics: A Foundation for Computer Science
Graham, R. L., Knuth, D. E., Patashnik, O., & Liu, S. (1989) · Computers in Physics · doi:10.1063/1.4822863 · Cited by 2,407
Online Computation and Competitive Analysis
Borodin, A., & El‐Yaniv, R. (1998) · Cited by 2,333
Iterative Methods for the Solution of Equations.
Young, D. M., & Traub, J. F. (1967) · The American Mathematical Monthly · doi:10.2307/2316079 · Cited by 2,165
(2000) · Choice Reviews Online · doi:10.5860/choice.37-5723 · Cited by 1,617
Analytic Theory of Continued Fractions
Wall, H. S. (1967) · Cited by 1,401
Asymptotic methods in analysis
de Bruijn, N. G. (1958) · International Linear Collider · Cited by 1,332
Rounding errors in algebraic processes
(1964) · Journal of the Franklin Institute · doi:10.1016/0016-0032(64)90390-4 · Cited by 1,315
Khinchin, A. I. (1963) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 1,288
Computational Frameworks for the Fast Fourier Transform
Van Loan, C. (1992) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970999 · Cited by 1,283
Speeding the Pollard and elliptic curve methods of factorization
Montgomery, P. L. (1987) · Mathematics of Computation · doi:10.1090/s0025-5718-1987-0866113-7 · Cited by 1,218
Schnelle Multiplikation großer Zahlen
Schönhage, A., & Strassen, V. (1971) · Computing · doi:10.1007/bf02242355 · Cited by 1,107
Bürgisser, P., Clausen, M., & Shokrollahi, M. A. (1997) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-662-03338-8 · Cited by 1,026
Hille, E. (1959) · International Linear Collider · Cited by 1,007
MPFR: A multiple-precision binary floating-point library with correct rounding
Fousse, L., Hanrot, G., Lefèvre, V., Pélissier, P., & Zimmermann, P. (2007) · ACM Transactions on Mathematical Software · doi:10.1145/1236463.1236468 · Cited by 952
Self-citationAgrawal, M., Kayal, N., & Saxena, N. (2004) · Annals of Mathematics · doi:10.4007/annals.2004.160.781 · Cited by 931
IEEE Standard for Binary Floating Point Arithmetic
Ieee, A. (1985) · Medical Entomology and Zoology · Cited by 886
VIII. The deferred approach to the limit
Richardson, L. F., & Gaunt, J. A. (1927) · Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character · doi:10.1098/rsta.1927.0008 · Cited by 839
Barrett, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-47721-7_24 · Cited by 753
(2005) · doi:10.1007/0-387-28979-8 · Cited by 719
Fast fourier transform and convolution algorithms
(1981) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(81)90075-6 · Cited by 679
Is Gauss Quadrature Better than Clenshaw–Curtis?
Trefethen, L. N. (2008) · SIAM Review · doi:10.1137/060659831 · Cited by 644
Double Exponential Formulas for Numerical Integration
Takahasi, H., & Mori, M. (1973) · Publications of the Research Institute for Mathematical Sciences · doi:10.2977/prims/1195192451 · Cited by 627
On computing the discrete Fourier transform
Winograd, S. (1978) · Mathematics of Computation · doi:10.1090/s0025-5718-1978-0468306-4 · Cited by 613
The numerical treatment of a single nonlinear equation
Householder, A. S. (1970) · CERN Document Server (European Organization for Nuclear Research) · Cited by 590
BiTR: Built-in Tamper Resilience
Choi, S. G., Kiayias, A., & Malkin, T. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-25385-0_40 · Cited by 590
Håstad, J. (1990) · Journal of Algorithms · doi:10.1016/0196-6774(90)90014-6 · Cited by 584
Discrete Fourier transforms when the number of data samples is prime
Rader, C. M. (1968) · Proceedings of the IEEE · doi:10.1109/proc.1968.6477 · Cited by 535
Elementary functions: algorithms and implementation
(1998) · Choice Reviews Online · doi:10.5860/choice.35-2759 · Cited by 531
Special Functions: An Introduction to the Classical Functions of Mathematical Physics
Τemme, N. Μ., & Zwillinger, D. I. (1997) · American Journal of Physics · doi:10.1119/1.18604 · Cited by 505
Computer Arithmetic: Volume III
Swartzlander, E. E., & Lemonds, C. E. (2015) · WORLD SCIENTIFIC eBooks · doi:10.1142/9467 · Cited by 470
The fast Fourier transform in a finite field
Pollard, J. M. (1971) · Mathematics of Computation · doi:10.1090/s0025-5718-1971-0301966-0 · Cited by 467
A linear filtering approach to the computation of discrete Fourier transform
Bluestein, L. (1970) · IEEE Transactions on Audio and Electroacoustics · doi:10.1109/tau.1970.1162132 · Cited by 462
Handbook of Floating-Point Arithmetic
Muller, J.-M., Brisebarre, N., de Dinechin, F., Jeannerod, C.-P., Lefèvre, V., Melquiond, G., Revol, N., Stehlé, D., & Torres, S. (2010) · Birkhäuser Boston eBooks · doi:10.1007/978-0-8176-4705-6 · Cited by 453
THE COMPUTATIONAL COMPLEXITY OF ALGEBRAIC AND NUMERIC PROBLEMS.
Borodin, A., & Munro, I. (1975) · CERN Document Server (European Organization for Nuclear Research) · Cited by 447
Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity
Borwein, J. M., & Borwein, P. (2011) · Medical Entomology and Zoology · Cited by 435
Fast Multiple-Precision Evaluation of Elementary Functions
Brent, R. P. (1976) · Journal of the ACM · doi:10.1145/321941.321944 · Cited by 365
Self-citationHandbook of Continued Fractions for Special Functions
(2008) · doi:10.1007/978-1-4020-6949-9 · Cited by 340
On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
Paterson, M. S., & Stockmeyer, L. J. (1973) · SIAM Journal on Computing · doi:10.1137/0202007 · Cited by 333
On the Minimum Computation Time of Functions
Cook, S. A., & Aanderaa, S. (1969) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1969-0249212-8 · Cited by 315
Fast Algorithms for Manipulating Formal Power Series
Brent, R. P., & Kung, H. T. (1978) · Journal of the ACM · doi:10.1145/322092.322099 · Cited by 285
Self-citationFürer, M. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250800 · Cited by 240
Fast implementations of RSA cryptography
Shand, M., & Vuillemin, J. (2002) · Proceedings of IEEE 11th Symposium on Computer Arithmetic · doi:10.1109/arith.1993.378085 · Cited by 221
Schnelle Multiplikation von Polynomen �ber K�rpern der Charakteristik 2
Sch�nhage, A. (1977) · Acta Informatica · doi:10.1007/bf00289470 · Cited by 192
Computational problems associated with Racah algebra
Stein, J. (1967) · Journal of Computational Physics · doi:10.1016/0021-9991(67)90047-2 · Cited by 172
Computational strategies for the Riemann zeta function
Borwein, J. M., Bradley, D. M., & Crandall, R. E. (2000) · Journal of Computational and Applied Mathematics · doi:10.1016/s0377-0427(00)00336-8 · Cited by 169
Experimentation in mathematics: computational paths to discovery
Borwein, J. M., Bailey, D. H., Borwein, J., Bailey, D., & Girgensohn, R. (2004) · Choice Reviews Online · doi:10.5860/choice.42-0995 · Cited by 160
Purdom, P. W., & Brown, C. A. (1995) · Medical Entomology and Zoology · Cited by 157
MULTIPLE-PRECISION ZERO-FINDING METHODS AND THE COMPLEXITY OF ELEMENTARY FUNCTION EVALUATION
Brent, R. P. (1976) · Elsevier eBooks · doi:10.1016/b978-0-12-697560-4.50014-9 · Cited by 154
Self-citationHow to Multiply Matrices Faster
(1984) · Lecture notes in computer science · doi:10.1007/3-540-13866-8 · Cited by 147
Approximations and complex multiplication according to Ramanujan
Chudnovsky, D. V., & Chudnovsky, G. V. (2000) · Springer eBooks · doi:10.1007/978-1-4757-3240-5_63 · Cited by 146
An Elementary View of Euler's Summation Formula
Apostol, T. M. (1999) · American Mathematical Monthly · doi:10.1080/00029890.1999.12005063 · Cited by 133
Fast multiplication and its applications
Bernstein, D. J. (2008) · Cambridge University Press eBooks · doi:10.1017/9781139049801.011 · Cited by 129
Euclid's Algorithm for Large Numbers
Lehmer, D. H. (1938) · American Mathematical Monthly · doi:10.1080/00029890.1938.11990797 · Cited by 128
van der Hoeven, J. (2002) · Journal of Symbolic Computation · doi:10.1006/jsco.2002.0562 · Cited by 111
A Linear Filtering Approach to the Computation of the Discrete Fourier Transform
(1969) · The MIT Press eBooks · doi:10.7551/mitpress/5222.003.0018 · Cited by 107
Kelley, J. E. (1959) · SIAM Review · doi:10.1137/1001041 · Cited by 103
Sorenson, J. (1994) · Journal of Algorithms · doi:10.1006/jagm.1994.1006 · Cited by 95
Computation of π Using Arithmetic-Geometric Mean
Salamin, E. (2000) · Springer eBooks · doi:10.1007/978-1-4757-3240-5_46 · Cited by 95
Schönhage, A. (1982) · Lecture notes in computer science · doi:10.1007/3-540-11607-9_1 · Cited by 93
An algorithm for modular exponentiation
Dimitrov, V. S., JULLIEN, G. A., & Miller, W. C. (1998) · Information Processing Letters · doi:10.1016/s0020-0190(98)00044-1 · Cited by 87
Fast modular transforms via division
Moenck, R. T., & Borodin, A. (1972) · Annual Symposium on Switching & Automata Theory · doi:10.1109/swat.1972.5 · Cited by 80
Borodin, A., & Moenck, R. T. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80029-2 · Cited by 79
The Middle Product Algorithm I
Hanrot, G., Quercia, M., & Zimmermann, P. (2004) · Applicable Algebra in Engineering Communication and Computing · doi:10.1007/s00200-003-0144-2 · Cited by 78
Self-citationFast algorithms: A multitape Turing machine implementation
Schönhage, A., Grotefeld, A. F. W., & Vetter, E. (1994) · Medical Entomology and Zoology · Cited by 75
Detecting perfect powers in essentially linear time
Bernstein, D. (1998) · Mathematics of Computation · doi:10.1090/s0025-5718-98-00952-1 · Cited by 59
Fast evaluation of holonomic functions
van der Hoeven, J. (1999) · Theoretical Computer Science · doi:10.1016/s0304-3975(98)00102-9 · Cited by 59
A Binary Recursive Gcd Algorithm
Stehlé, D., & Zimmermann, P. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24847-7_31 · Cited by 52
Self-citationHasenplaugh, W., Gaubatz, G., & Gopal, V. (2007) · IEEE Symposium on Computer Arithmetic (ARITH) · doi:10.1109/arith.2007.18 · Cited by 48
More on squaring and multiplying large integers
Zuras, D. (1994) · IEEE Transactions on Computers · doi:10.1109/12.295852 · Cited by 48
Chung, J., & Hasan, M. A. (2007) · IEEE Symposium on Computer Arithmetic (ARITH) · doi:10.1109/arith.2007.11 · Cited by 48
Integer and polynomial multiplication
Bodrato, M., & Zanoni, A. (2007) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/1277548.1277552 · Cited by 46
Massively parallel elliptic curve factoring
Dixon, B., & Lenstra, A. K. (2007) · Springer eBooks · doi:10.1007/3-540-47555-9_16 · Cited by 39
Fast multiprecision evaluation of series of rational numbers
Haible, B., & Papanikolaou, T. (1998) · Lecture notes in computer science · doi:10.1007/bfb0054873 · Cited by 37
Newton’s method and FFT trading
van der Hoeven, J. (2010) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2010.03.005 · Cited by 37
On infinitely precise rounding for division, square root, reciprocal and square root reciprocal
Iordache, C., & Matula, D. W. (2003) · Proceedings/Proceedings - Symposium on Computer Arithmetic · doi:10.1109/arith.1999.762849 · Cited by 35
Modular exponentiation via the explicit Chinese remainder theorem
Bernstein, D. J., & Sorenson, J. (2006) · Mathematics of Computation · doi:10.1090/s0025-5718-06-01849-7 · Cited by 35
Error bounds on complex floating-point multiplication
Brent, R. P., Percival, C., & Zimmermann, P. (2007) · Mathematics of Computation · doi:10.1090/s0025-5718-07-01931-x · Cited by 33
Self-citationVepštas, L. (2008) · Numerical Algorithms · doi:10.1007/s11075-007-9153-8 · Cited by 31
Some New Algorithms for High-Precision Computation of Euler’s Constant
Brent, R. P., & McMillan, E. M. (2004) · Springer eBooks · doi:10.1007/978-1-4757-4217-6_50 · Cited by 27
Self-citationSpace- and time-efficient polynomial multiplication
Roche, D. S. (2009) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/1576702.1576743 · Cited by 27
A multimodular algorithm for computing Bernoulli numbers
Harvey, D. (2010) · Mathematics of Computation · doi:10.1090/s0025-5718-2010-02367-1 · Cited by 27
Efficient Algorithms for Computing the Jacobi Symbol
Eikenberry, S. M., & Sorenson, J. (1998) · Journal of Symbolic Computation · doi:10.1006/jsco.1998.0226 · Cited by 25
A note on square roots in finite fields
Bach, E. (1990) · IEEE Transactions on Information Theory · doi:10.1109/18.59955 · Cited by 21
Faster algorithms for the square root and reciprocal of power series
Harvey, D. (2010) · Mathematics of Computation · doi:10.1090/s0025-5718-2010-02392-0 · Cited by 17
Dynamical zeta functions and Kummer congruences
de Reyna, J. A. (2005) · Acta Arithmetica · doi:10.4064/aa119-1-3 · Cited by 13
Time-and space-efficient evaluation of some hypergeometric constants
Cheng, H., Hanrot, G., Thomé, E., Zimmermann, P., & Zima, E. V. (2007) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/1277548.1277561 · Cited by 11
Self-citationFast convolutions meet Montgomery
Mihăilescu, P. (2007) · Mathematics of Computation · doi:10.1090/s0025-5718-07-01956-4 · Cited by 5
Cited by
Exponentially more precise quantum simulation of fermions in second quantization
Babbush, R., Berry, D. W., Kivlichan, I. D., Wei, A. Y., Love, P. J., & Aspuru-Guzik, A. (2016) · New Journal of Physics · doi:10.1088/1367-2630/18/3/033032 · Cited by 135
Metadata
- Authors
- Brent, R. P., & Zimmermann, P.
- Venue
- Cambridge University Press eBooks
- Publisher
- Cambridge University Press
- Published
- 2010-11-25
- OpenAlex
- W2131286165
- Cited by
- 321
- References
- 104
- FWCI
- 7.39
- Type
- book
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.