Computational complexity of mathematical operations
From Wikipedia, the free encyclopedia
The following tables list the computational complexity of various algorithms for common mathematical operations.
Here, complexity refers to the time complexity of performing computations on a random access machine. See big O notation for an explanation of the notation used.
Contents |
[edit] Arithmetic and algebraic functions
| Operation | Input | Output | Algorithm | Complexity |
|---|---|---|---|---|
| Addition | Two n-digit numbers | One n+1-digit number | Schoolbook addition | O(n) |
| Subtraction | Two n-digit numbers | One n+1-digit number | Schoolbook subtraction | O(n) |
| Multiplication | Two n-digit numbers |
One 2n-digit number | Schoolbook multiplication | O(n2) |
| Karatsuba multiplication | O(n1.585) | |||
| 3-way Toom-Cook multiplication | O(n1.465) | |||
| k-way Toom-Cook multiplication | O(n1 + ε),ε > 0 | |||
| Mixed-level Toom-Cook (Knuth 4.3.3-T)[1] | O(n 2√(2 log n) (log n)) | |||
| Schönhage-Strassen multiplication | O(n (log n) (log log n)) | |||
| Note: The complexity of multiplication will be referred to as M(n) below | ||||
| Division | Two n-digit numbers | One n-digit number | Schoolbook division | O(n2) |
| Newton's method | M(n) | |||
| Square root | One n-digit number | One n-digit number | Newton's method | M(n) |
| Polynomial evaluation | n fixed-size polynomial coefficients | One fixed-size number | Horner's method | O(n) |
| Direct evaluation | O(n) | |||
Schnorr and Stumpf [2] conjectured that no fastest algorithm for multiplication exists.
[edit] Special functions
The methods in this section are given in Borwein & Borwein.[3]
[edit] Elementary functions
The elementary functions are constructed by composing arithmetic operations, the exponential function (exp), the natural logarithm (log), trigonometric functions (sin, cos), 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 exp or log can be computed with some complexity, then that complexity is attainable for all other elementary functions.
Below, the size n 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. exp(2x) = [exp(x)]2]) and direct summation | exp, log, sin, cos | O(n1/2 M(n)) |
| Taylor series; FFT-based acceleration | exp, log, sin, cos | O(n1/3 (log n)2 M(n)) |
| Taylor series; binary splitting | exp, log, sin, cos | O((log n)2 M(n)) |
| Arithmetic-geometric mean iteration | log | O((log n) M(n)) |
It is not known whether O((log n) M(n)) is the optimal complexity for elementary functions. The best known lower bound is the trivial bound O(M(n)).
[edit] Non-elementary functions
| Function | Input | Algorithm | Complexity |
|---|---|---|---|
| Gamma function | n-digit number | Series approximation of the incomplete gamma function | O(n1/2 (log n)2 M(n)) |
| Fixed rational number | Hypergeometric series | O((log n)2 M(n)) | |
| m/24, m an integer | Arithmetic-geometric mean iteration | O((log n) M(n)) | |
| Hypergeometric function pFq | n-digit number | (As described in Borwein & Borwein) | O(n1/2 (log n)2 M(n)) |
| Fixed rational number | Hypergeometric series | O((log n)2 M(n)) |
[edit] Mathematical constants
This table gives the complexity of computing approximations to the given constants to n correct digits.
| Constant | Algorithm | Complexity |
|---|---|---|
| Golden ratio, φ | Newton's method | O(M(n)) |
| Square root of 2, √2 | Newton's method | O(M(n)) |
| Euler's number, e | Binary splitting of the Taylor series for the exponential function | O((log n) M(n)) |
| Newton inversion of the natural logarithm | O((log n) M(n)) | |
| Pi, π | Binary splitting of the arctan series in Machin's formula | O((log n)2 M(n)) |
| Arithmetic-geometric mean iteration | O((log n) M(n)) | |
| Euler's constant, γ | Sweeney's method (approximation in terms of the exponential integral) | O((log n)2 M(n)) |
[edit] Number theory
Algorithms for number-theoretical calculations are studied in computational number theory.
| Operation | Input | Output | Algorithm | Complexity |
|---|---|---|---|---|
| Greatest common divisor | Two n-digit numbers | One number with at most n digits | Euclidean algorithm | O(n2) |
| Binary GCD algorithm | O(n2) | |||
| Stehlé-Zimmermann algorithm[4] | O((log n) M(n)) | |||
| Schönhage Controlled Euclidean Descent algorithm[5] | O((log n) M(n)) | |||
| Factorial[6] | A fixed-size number m | One O((m+1/2)(log m) - m)-digit number | Bottom-up multiplication | O(m2 log m) |
| Binary splitting | O((log m) M(m log m)) | |||
| Exponentiation of the prime factors of m | O((log log m) M(m log m)) |
[edit] 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.
| Operation | Input | Output | Algorithm | Complexity |
|---|---|---|---|---|
| Matrix multiplication | Two n×n-matrices | One n×n-matrix | Schoolbook matrix multiplication | O(n3) |
| Strassen algorithm | O(n2.807) | |||
| Coppersmith–Winograd algorithm | O(n2.376) | |||
| Matrix inversion | One n×n-matrix | One n×n-matrix | Gaussian elimination | O(n3) |
| Coppersmith–Winograd algorithm | O(n2.376) |
Henry Cohn, Robert Kleinberg, Balázs Szegedy and Christopher Umans show that either of two different conjectures would imply that the exponent of matrix multiplication is 2.[7] It has also been conjectured that no fastest algorithm for matrix multiplication exists, in light of the nearly 20 successive improvements leading to the Coppersmith-Winograd algorithm.
[edit] References
- ^ D. Knuth. The Art of Computer Programming, Volume 2. Third Edition, Addison-Wesley 1997.
- ^ C.P.Schnorr and G. Stumpf. A characterization of complexity sequences. Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik 21(1):47--56, 1975.
- ^ J. Borwein & P. Borwein. Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. John Wiley 1987.
- ^ R. Crandall & C. Pomerance. Prime Numbers - A Computational Perspective. Second Edition, Springer 2005.
- ^ N. Möller. "On Schönhage's algorithm and subquadratic integer gcd computation", preprint.
- ^ P. Borwein. "On the Complexity of Calculating Factorials". Journal of Algorithms 6, 376-380 (1985)
- ^ 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.
