Computational complexity of mathematical operations

Summary

The following tables list the computational complexity of various algorithms for common mathematical operations.

Graphs of functions commonly used in the analysis of algorithms, showing the number of operations versus input size for each function

Here, complexity refers to the time complexity of performing computations on a multitape Turing machine.[1] See big O notation for an explanation of the notation used.

Note: Due to the variety of multiplication algorithms, below stands in for the complexity of the chosen multiplication algorithm.

Arithmetic functionsEdit

Operation Input Output Algorithm Complexity
Addition Two  -digit numbers,   and   One  -digit number Schoolbook addition with carry  
Subtraction Two  -digit numbers,   and   One  -digit number Schoolbook subtraction with borrow  
Multiplication Two  -digit numbers
One  -digit number Schoolbook long multiplication  
Karatsuba algorithm  
3-way Toom–Cook multiplication  
 -way Toom–Cook multiplication  
Mixed-level Toom–Cook (Knuth 4.3.3-T)[2]  
Schönhage–Strassen algorithm  
Fürer's algorithm[3]  
Harvey-Hoeven algorithm[4][5]  
Division Two  -digit numbers One  -digit number Schoolbook long division  
Burnikel–Ziegler Divide-and-Conquer Division[6]  
Newton–Raphson division  
Square root One  -digit number One  -digit number Newton's method  
Modular exponentiation Two  -digit integers and a  -bit exponent One  -digit integer Repeated multiplication and reduction  
Exponentiation by squaring  
Exponentiation with Montgomery reduction  

Algebraic functionsEdit

Operation Input Output Algorithm Complexity
Polynomial evaluation One polynomial of degree   with fixed-size coefficients One fixed-size number Direct evaluation  
Horner's method  
Polynomial gcd (over   or  ) Two polynomials of degree   with fixed-size integer coefficients One polynomial of degree at most   Euclidean algorithm  
Fast Euclidean algorithm (Lehmer)[7]  

Special functionsEdit

Many of the methods in this section are given in Borwein & Borwein.[8]

Elementary functionsEdit

The elementary functions are constructed by composing arithmetic operations, the exponential function ( ), the natural logarithm ( ), trigonometric functions ( ), and their inverses. The complexity of an elementary function is equivalent to that of its inverse, since all elementary functions are analytic and hence invertible by means of Newton's method. In particular, if either   or   in the complex domain can be computed with some complexity, then that complexity is attainable for all other elementary functions.

Below, the size   refers to the number of digits of precision at which the function is to be evaluated.

Algorithm Applicability Complexity
Taylor series; repeated argument reduction (e.g.  ) and direct summation    
Taylor series; FFT-based acceleration    
Taylor series; binary splitting + bit-burst algorithm[9]    
Arithmetic–geometric mean iteration[10]    

It is not known whether   is the optimal complexity for elementary functions. The best known lower bound is the trivial bound   .

Non-elementary functionsEdit

Function Input Algorithm Complexity
Gamma function  -digit number Series approximation of the incomplete gamma function  
Fixed rational number Hypergeometric series  
 , for   integer. Arithmetic-geometric mean iteration  
Hypergeometric function    -digit number (As described in Borwein & Borwein)  
Fixed rational number Hypergeometric series  

Mathematical constantsEdit

This table gives the complexity of computing approximations to the given constants to   correct digits.

Constant Algorithm Complexity
Golden ratio,   Newton's method  
Square root of 2,   Newton's method  
Euler's number,   Binary splitting of the Taylor series for the exponential function  
Newton inversion of the natural logarithm  
Pi,   Binary splitting of the arctan series in Machin's formula  [11]
Gauss–Legendre algorithm  [11]
Euler's constant,   Sweeney's method (approximation in terms of the exponential integral)  

Number theoryEdit

Algorithms for number theoretical calculations are studied in computational number theory.

Operation Input Output Algorithm Complexity
Greatest common divisor Two  -digit integers One integer with at most   digits Euclidean algorithm  
Binary GCD algorithm  
Left/right k-ary binary GCD algorithm[12]  
Stehlé–Zimmermann algorithm[13]  
Schönhage controlled Euclidean descent algorithm[14]  
Jacobi symbol Two  -digit integers  ,   or   Schönhage controlled Euclidean descent algorithm[15]  
Stehlé–Zimmermann algorithm[16]  
Factorial A positive integer less than   One  -digit integer Bottom-up multiplication  
Binary splitting  
Exponentiation of the prime factors of    ,[17]
 [1]
Primality test A  -digit integer True or false AKS primality test  [18][19] or  ,[20][21]
 , assuming Agrawal's conjecture
Elliptic curve primality proving   heuristically[22]
Baillie–PSW primality test  [23][24]
Miller–Rabin primality test  [25]
Solovay–Strassen primality test  [25]
Integer factorization A  -bit input integer A set of factors General number field sieve  [nb 1]
Shor's algorithm  , on a quantum computer

Matrix algebraEdit

The following complexity figures assume that arithmetic with individual elements has complexity O(1), as is the case with fixed-precision floating-point arithmetic or operations on a finite field.

Operation Input Output Algorithm Complexity
Matrix multiplication Two   matrices One   matrix Schoolbook matrix multiplication  
Strassen algorithm  
Coppersmith–Winograd algorithm (galactic algorithm)  
Optimized CW-like algorithms[26][27][28][29] (galactic algorithms)  
Matrix multiplication One   matrix & one   matrix One   matrix Schoolbook matrix multiplication  
Matrix multiplication One   matrix &

one   matrix, for some  

One   matrix Algorithms given in [30]  , where upper bounds on   are given in [30]
Matrix inversion* One   matrix One   matrix Gauss–Jordan elimination  
Strassen algorithm  
Coppersmith–Winograd algorithm  
Optimized CW-like algorithms  
Singular value decomposition One   matrix One   matrix,
one   matrix, &
one   matrix
Bidiagonalization and QR algorithm  
( )
One   matrix,
one   matrix, &
one   matrix
Bidiagonalization and QR algorithm  
( )
Determinant One   matrix One number Laplace expansion  
Division-free algorithm[31]  
LU decomposition  
Bareiss algorithm  
Fast matrix multiplication[32]  
Back substitution Triangular matrix   solutions Back substitution[33]  

In 2005, Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Chris Umans showed that either of two different conjectures would imply that the exponent of matrix multiplication is 2.[34]

TransformsEdit

Algorithms for computing transforms of functions (particularly integral transforms) are widely used in all areas of mathematics, particularly analysis and signal processing.

Operation Input Output Algorithm Complexity
Discrete Fourier transform Finite data sequence of size   Set of complex numbers Fast Fourier transform  

NotesEdit

  1. ^ This form of sub-exponential time is valid for all  . A more precise form of the complexity can be given as  

ReferencesEdit

  1. ^ a b A. Schönhage, A.F.W. Grotefeld, E. Vetter: Fast Algorithms—A Multitape Turing Machine Implementation, BI Wissenschafts-Verlag, Mannheim, 1994
  2. ^ D. Knuth. The Art of Computer Programming, Volume 2. Third Edition, Addison-Wesley 1997.
  3. ^ Martin Fürer. Faster Integer Multiplication [https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf Archived 2013-04-25 at the Wayback Machine. Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11–13, 2007, pp. 55–67.
  4. ^ David Harvey, Joris van der Hoeven Integer multiplication in time O (n log n). (2019).
  5. ^ Erica Klarreich. 2019. Multiplication hits the speed limit. Commun. ACM 63, 1 (December 2019), 11–13. doi:10.1145/3371387
  6. ^ Christoph Burnikel and Joachim Ziegler Fast Recursive Division Im Stadtwald, D- Saarbrucken 1998.
  7. ^ "Fast Euclidean algorithm".
  8. ^ J. Borwein & P. Borwein. Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. John Wiley 1987.
  9. ^ David and Gregory Chudnovsky. Approximations and complex multiplication according to Ramanujan. Ramanujan revisited, Academic Press, 1988, pp 375–472.
  10. ^ Richard P. Brent, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, in: Analytic Computational Complexity (J. F. Traub, ed.), Academic Press, New York, 1975, 151–176.
  11. ^ a b Richard P. Brent (2020), The Borwein Brothers, Pi and the AGM, Springer Proceedings in Mathematics & Statistics, vol. 313, arXiv:1802.07558, doi:10.1007/978-3-030-36568-4, ISBN 978-3-030-36567-7, S2CID 214742997
  12. ^ J. Sorenson. (1994). "Two Fast GCD Algorithms". Journal of Algorithms. 16 (1): 110–144. doi:10.1006/jagm.1994.1006.
  13. ^ R. Crandall & C. Pomerance. Prime Numbers – A Computational Perspective. Second Edition, Springer 2005.
  14. ^ Möller N (2008). "On Schönhage's algorithm and subquadratic integer gcd computation" (PDF). Mathematics of Computation. 77 (261): 589–607. Bibcode:2008MaCom..77..589M. doi:10.1090/S0025-5718-07-02017-0.
  15. ^ Bernstein D J. "Faster Algorithms to Find Non-squares Modulo Worst-case Integers".
  16. ^ Richard P. Brent; Paul Zimmermann (2010). "An   algorithm for the Jacobi symbol". arXiv:1004.2091 [cs.DS].
  17. ^ Borwein, P. (1985). "On the complexity of calculating factorials". Journal of Algorithms. 6 (3): 376–380. doi:10.1016/0196-6774(85)90006-9.
  18. ^ H. W. Lenstra Jr. and Carl Pomerance, "Primality testing with Gaussian periods", preliminary version July 20, 2005.
  19. ^ H. W. Lenstra jr. and Carl Pomerance, "Primality testing with Gaussian periods Archived 2012-02-25 at the Wayback Machine", version of April 12, 2011.
  20. ^ Tao, Terence (2010). "1.11 The AKS primality test". An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics. Vol. 117. Providence, RI: American Mathematical Society. pp. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4. MR 2780010.
  21. ^ Lenstra, Jr., H.W.; Pomerance, Carl (December 11, 2016). "Primality testing with Gaussian periods" (PDF).
  22. ^ Morain, F. (2007). "Implementing the asymptotically fast version of the elliptic curve primality proving algorithm". Mathematics of Computation. 76 (257): 493–505. arXiv:math/0502097. Bibcode:2007MaCom..76..493M. doi:10.1090/S0025-5718-06-01890-4. MR 2261033. S2CID 133193.
  23. ^ Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·109" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7. JSTOR 2006210.
  24. ^ Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "Lucas Pseudoprimes" (PDF). Mathematics of Computation. 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. JSTOR 2006406. MR 0583518.
  25. ^ a b Monier, Louis (1980). "Evaluation and comparison of two efficient probabilistic primality testing algorithms". Theoretical Computer Science. 12 (1): 97–108. doi:10.1016/0304-3975(80)90007-9. MR 0582244.
  26. ^ Alman, Josh; Williams, Virginia Vassilevska (2020), "A Refined Laser Method and Faster Matrix Multiplication", 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), arXiv:2010.05846
  27. ^ Davie, A.M.; Stothers, A.J. (2013), "Improved bound for complexity of matrix multiplication", Proceedings of the Royal Society of Edinburgh, 143A (2): 351–370, doi:10.1017/S0308210511001648, S2CID 113401430
  28. ^ Vassilevska Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier (PDF)
  29. ^ Le Gall, François (2014), "Powers of tensors and fast matrix multiplication", Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation - ISSAC '14, p. 23, arXiv:1401.7714, Bibcode:2014arXiv1401.7714L, doi:10.1145/2608628.2627493, ISBN 9781450325011, S2CID 353236
  30. ^ a b Le Gall, François; Urrutia, Floren (2018). "Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor". In Czumaj, Artur (ed.). Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics (SIAM). doi:10.1137/1.9781611975031.67. ISBN 978-1-61197-503-1. S2CID 33396059.
  31. ^ http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf[bare URL PDF]
  32. ^ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms, Addison-Wesley, Theorem 6.6, p. 241
  33. ^ J. B. Fraleigh and R. A. Beauregard, "Linear Algebra," Addison-Wesley Publishing Company, 1987, p 95.
  34. ^ Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. arXiv:math.GR/0511460. Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23–25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388.

Further readingEdit