Computational complexity of mathematical operations
This article needs additional citations for verification. (April 2015) |
The following tables list the
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 functions
This table lists the complexity of mathematical operations on integers.
Operation | Input | Output | Algorithm | Complexity |
---|---|---|---|---|
Addition | Two -digit numbers | One -digit number | Schoolbook addition with carry | |
Subtraction | Two -digit numbers | 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 | ||||
Division | Two -digit numbers | One -digit number | Schoolbook long division | |
Burnikel–Ziegler Divide-and-Conquer Division[5] | ||||
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
|
On stronger computational models, specifically a pointer machine and consequently also a unit-cost random-access machine it is possible to multiply two n-bit numbers in time O(n).[6]
Algebraic functions
Here we consider operations over polynomials and n denotes their degree; for the coefficients we use a unit-cost model, ignoring the number of bits in a number. In practice this means that we assume them to be machine integers.
Operation | Input | Output | Algorithm | Complexity |
---|---|---|---|---|
Polynomial evaluation | One polynomial of degree with integer coefficients | One number | Direct evaluation | |
Horner's method | ||||
Polynomial gcd (over or ) | Two polynomials of degree with integer coefficients | One polynomial of degree at most | Euclidean algorithm | |
Fast Euclidean algorithm (Lehmer)[citation needed] |
Special functions
Many of the methods in this section are given in Borwein & Borwein.[7]
Elementary functions
The elementary functions are constructed by composing arithmetic operations, the exponential function (), the natural logarithm (),
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[8] | ||
Arithmetic–geometric mean iteration[9] |
It is not known whether is the optimal complexity for elementary functions. The best known lower bound is the trivial bound .
Non-elementary functions
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 constants
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
|
[10] |
Gauss–Legendre algorithm | [10] | |
Euler's constant ,
|
Sweeney's method (approximation in terms of the exponential integral) |
Number theory
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[11] | ||||
Stehlé–Zimmermann algorithm[12] | ||||
Schönhage controlled Euclidean descent algorithm[13] | ||||
Jacobi symbol | Two -digit integers | , or | Schönhage controlled Euclidean descent algorithm[14] | |
Stehlé–Zimmermann algorithm[15] | ||||
Factorial | A positive integer less than | One -digit integer | Bottom-up multiplication | |
Binary splitting | ||||
Exponentiation of the prime factors of | ,[16] [1] | |||
Primality test | A -digit integer | True or false | AKS primality test | [17][18] , assuming Agrawal's conjecture |
Elliptic curve primality proving
|
heuristically[19] | |||
Baillie–PSW primality test | [20][21] | |||
Miller–Rabin primality test | [22] | |||
Solovay–Strassen primality test | [22] | |||
Integer factorization | A -bit input integer | A set of factors | General number field sieve | [nb 1] |
Shor's algorithm | , on a quantum computer
|
Matrix algebra
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[23][24][25][26] (galactic algorithms) | ||||
Matrix multiplication | One matrix, and one matrix |
One matrix | Schoolbook matrix multiplication | |
Matrix multiplication | One matrix, and one matrix, for some |
One matrix | Algorithms given in [27] | , where upper bounds on are given in [27] |
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 | () | ||
QR decomposition | One matrix | One matrix, & one matrix |
Algorithms in [28] | () |
Determinant | One matrix | One number | Laplace expansion | |
Division-free algorithm[29] | ||||
LU decomposition | ||||
Bareiss algorithm | ||||
Fast matrix multiplication[30] | ||||
Back substitution | Triangular matrix | solutions | Back substitution[31] |
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.[32]
Transforms
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 | Schoolbook | |
Fast Fourier transform |
Notes
- ^ This form of sub-exponential time is valid for all . A more precise form of the complexity can be given as
References
- ^ OCLC 897602049.
- ^ Knuth 1997
- S2CID 109934776.
- S2CID 209450552.
- OCLC 246319574. MPII-98-1-022.
- doi:10.1137/0209036.
- OCLC 755165897.
- ISBN 978-0-01-205856-5.
- ISBN 978-1-4832-5789-1.
- ^ S2CID 214742997
- .
- ISBN 978-0-387-28979-3.
- .
- ^ Bernstein, D.J. "Faster Algorithms to Find Non-squares Modulo Worst-case Integers".
- ^ Brent, Richard P.; Zimmermann, Paul (2010). "An algorithm for the Jacobi symbol". International Algorithmic Number Theory Symposium. Springer. pp. 83–95. S2CID 7632655.
- .
- .
- MR 2780010.
- S2CID 133193.
- JSTOR 2006210.
- MR 0583518.
- ^ MR 0582244.
- ^
Alman, Josh; Williams, Virginia Vassilevska (2020), "A Refined Laser Method and Faster Matrix Multiplication", 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), S2CID 222290442
- S2CID 113401430
- ^ Vassilevska Williams, Virginia (2014), Breaking the Coppersmith-Winograd barrier: Multiplying matrices in O(n2.373) time
- S2CID 353236
- ^ S2CID 33396059.
- ISSN 0024-3795.
- ISBN 3-540-45506-X.
- ISBN 978-0-201-00029-0.
- ISBN 978-0-201-15459-7.
- S2CID 6429088.
Further reading
- ISBN 978-0-521-19469-3.
- ISBN 978-0-201-89684-8.