Computational complexity of mathematical operations: Difference between revisions

Content deleted Content added

Inline

Revision as of 00:57, 8 November 2022

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 multitape Turing machine.^[1] See big O notation for an explanation of the notation used.

Note: Due to the variety of multiplication algorithms, $M(n)$ below stands in for the complexity of the chosen multiplication algorithm.

Arithmetic functions

Operation	Input	Output	Algorithm	Complexity
Addition	Two $n$ -digit numbers, $N$ and $N$	One $n+1$ -digit number	Schoolbook addition with carry	$\Theta (n),\Theta (\log(N))$
Subtraction	Two $n$ -digit numbers, $N$ and $N$	One $n+1$ -digit number	Schoolbook subtraction with borrow	$\Theta (n),\Theta (\log(N))$
Multiplication	Two $n$ -digit numbers	One $2n$ -digit number	Schoolbook long multiplication	$O{\mathord {\left(n^{2}\right)}}$
			Karatsuba algorithm	$O{\mathord {\left(n^{1.585}\right)}}$
			3-way Toom–Cook multiplication	$O{\mathord {\left(n^{1.465}\right)}}$
			$k$ -way Toom–Cook multiplication	$O{\mathord {\left(n^{\frac {\log(2k-1)}{\log k}}\right)}}$
			Mixed-level Toom–Cook (Knuth 4.3.3-T)^[2]	$O{\mathord {\left(n\,2^{\sqrt {2\log n}}\,\log n\right)}}$
			Schönhage–Strassen algorithm	$O{\mathord {\left(n\log n\log \log n\right)}}$
			Harvey-Hoeven algorithm^[3]^[4]	$O(n\log n)$
Division	Two $n$ -digit numbers	One $n$ -digit number	Schoolbook long division	$O{\mathord {\left(n^{2}\right)}}$
			Burnikel–Ziegler Divide-and-Conquer Division^[5]	$O(M(n)\log n)$
			Newton–Raphson division	$O(M(n))$
Square root	One $n$ -digit number	One $n$ -digit number	Newton's method	$O(M(n))$
Modular exponentiation	Two $n$ -digit integers and a $k$ -bit exponent	One $n$ -digit integer	Repeated multiplication and reduction	$O{\mathord {\left(M(n)\,2^{k}\right)}}$
			Exponentiation by squaring	$O(M(n)\,k)$
			Exponentiation with Montgomery reduction	$O(M(n)\,k)$

Algebraic functions

Operation	Input	Output	Algorithm	Complexity
Polynomial evaluation	One polynomial of degree $n$ with fixed-size coefficients	One fixed-size number	Direct evaluation	$\Theta (n)$
Polynomial evaluation	One polynomial of degree $n$ with fixed-size coefficients	One fixed-size number	Horner's method	$\Theta (n)$
Polynomial gcd (over $\mathbb {Z} [x]$ or $F[x]$ )	Two polynomials of degree $n$ with fixed-size integer coefficients	One polynomial of degree at most $n$	Euclidean algorithm	$O{\mathord {\left(n^{2}\right)}}$
Polynomial gcd (over $\mathbb {Z} [x]$ or $F[x]$ )		One polynomial of degree at most $n$	Fast Euclidean algorithm (Lehmer)^[6]	$O(M(n)\log n)$

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 ( $\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$ in the complex domain 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 ,\arctan$	$O{\mathord {\left(M(n)n^{1/2}\right)}}$
Taylor series; FFT-based acceleration	$\exp ,\log ,\sin ,\cos ,\arctan$	$O{\mathord {\left(M(n)n^{1/3}(\log n)^{2}\right)}}$
Taylor series; binary splitting + bit-burst algorithm^[8]	$\exp ,\log ,\sin ,\cos ,\arctan$	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$
Arithmetic–geometric mean iteration^[9]	$\exp ,\log ,\sin ,\cos ,\arctan$	$O(M(n)\log n)$

It is not known whether $O(M(n)\log n)$ is the optimal complexity for elementary functions. The best known lower bound is the trivial bound $\Omega$ $(M(n))$ .

Non-elementary functions

Function	Input	Algorithm	Complexity
Gamma function	$n$ -digit number	Series approximation of the incomplete gamma function	$O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}$
	Fixed rational number	Hypergeometric series	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$
	$m/24$ , for $m$ integer.	Arithmetic-geometric mean iteration	$O(M(n)\log n)$
Hypergeometric function ${}_{p}\!F_{q}$	$n$ -digit number	(As described in Borwein & Borwein)	$O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}$
Hypergeometric function ${}_{p}\!F_{q}$	Fixed rational number	Hypergeometric series	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$

Mathematical constants

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

Constant	Algorithm	Complexity
Golden ratio, $\phi$	Newton's method	$O(M(n))$
Square root of 2, ${\sqrt {2}}$	Newton's method	$O(M(n))$
Euler's number, $e$	Binary splitting of the Taylor series for the exponential function	$O(M(n)\log n)$
Euler's number, $e$	Newton inversion of the natural logarithm	$O(M(n)\log n)$
Pi, $\pi$	Binary splitting of the arctan series in Machin's formula	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$ ^[10]
Pi, $\pi$	Gauss–Legendre algorithm	$O(M(n)\log n)$ ^[10]
Euler's constant, $\gamma$	Sweeney's method (approximation in terms of the exponential integral)	$O{\mathord {\left(M(n)(\log n)^{2}\right)}}$

Number theory

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

Operation	Input	Output	Algorithm	Complexity
Greatest common divisor	Two $n$ -digit integers	One integer with at most $n$ digits	Euclidean algorithm	$O{\mathord {\left(n^{2}\right)}}$
			Binary GCD algorithm	$O{\mathord {\left(n^{2}\right)}}$
			Left/right k-ary binary GCD algorithm^[11]	$O{\mathord {\left({\frac {n^{2}}{\log n}}\right)}}$
			Stehlé–Zimmermann algorithm^[12]	$O(M(n)\log n)$
			Schönhage controlled Euclidean descent algorithm^[13]	$O(M(n)\log n)$
Jacobi symbol	Two $n$ -digit integers	$0$ , $-1$ or $1$	Schönhage controlled Euclidean descent algorithm^[14]	$O(M(n)\log n)$
Jacobi symbol	Two $n$ -digit integers	$0$ , $-1$ or $1$	Stehlé–Zimmermann algorithm^[15]	$O(M(n)\log n)$
Factorial	A positive integer less than $m$	One $O(m\log m)$ -digit integer	Bottom-up multiplication	$O{\mathord {\left(M\left(m^{2}\right)\log m\right)}}$
			Binary splitting	$O(M(m\log m)\log m)$
			Exponentiation of the prime factors of $m$	$O(M(m\log m)\log \log m)$ ,^[16] $O(M(m\log m))$ ^[1]
Primality test	A $n$ -digit integer	True or false	AKS primality test	$O{\mathord {\left(n^{6+o(1)}\right)}}$ ^[17]^[18]^[17] $O(n^{3})$ , assuming Agrawal's conjecture
			Elliptic curve primality proving	$O{\mathord {\left(n^{4+\varepsilon }\right)}}$ heuristically^[19]
			Baillie–PSW primality test	$O{\mathord {\left(n^{2+\varepsilon }\right)}}$ ^[20]^[21]
			Miller–Rabin primality test	$O{\mathord {\left(kn^{2+\varepsilon }\right)}}$ ^[22]
			Solovay–Strassen primality test	$O{\mathord {\left(kn^{2+\varepsilon }\right)}}$ ^[22]
Integer factorization	A $b$ -bit input integer	A set of factors	General number field sieve	$O{\mathord {\left((1+\varepsilon )^{b}\right)}}$ ^{[nb 1]}
Integer factorization	A $b$ -bit input integer	A set of factors	Shor's algorithm	$O(M(b)b)$ , 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 $n\times n$ matrices	One $n\times n$ matrix	Schoolbook matrix multiplication	$O(n^{3})$
			Strassen algorithm	$O{\mathord {\left(n^{2.807}\right)}}$
			Coppersmith–Winograd algorithm (galactic algorithm)	$O{\mathord {\left(n^{2.376}\right)}}$
			Optimized CW-like algorithms^[23]^[24]^[25]^[26] (galactic algorithms)	$O{\mathord {\left(n^{2.3728596}\right)}}$
Matrix multiplication	One $n\times m$ matrix, and one $m\times p$ matrix	One $n\times p$ matrix	Schoolbook matrix multiplication	$O(nmp)$
Matrix multiplication	One $n\times \left\lceil n^{k}\right\rceil$ matrix, and one $\left\lceil n^{k}\right\rceil \times n$ matrix, for some $k\geq 0$	One $n\times n$ matrix	Algorithms given in ^[27]	$O(n^{\omega (k)+\epsilon })$ , where upper bounds on $\omega (k)$ are given in ^[27]
Matrix inversion	One $n\times n$ matrix	One $n\times n$ matrix	Gauss–Jordan elimination	$O{\mathord {\left(n^{3}\right)}}$
			Strassen algorithm	$O{\mathord {\left(n^{2.807}\right)}}$
			Coppersmith–Winograd algorithm	$O{\mathord {\left(n^{2.376}\right)}}$
			Optimized CW-like algorithms	$O{\mathord {\left(n^{2.373}\right)}}$
Singular value decomposition	One $m\times n$ matrix	One $m\times m$ matrix, one $m\times n$ matrix, & one $n\times n$ matrix	Bidiagonalization and QR algorithm	$O{\mathord {\left(m^{2}n\right)}}$ ( $m\geq n$ )
Singular value decomposition	One $m\times n$ matrix	One $m\times n$ matrix, one $n\times n$ matrix, & one $n\times n$ matrix	Bidiagonalization and QR algorithm	$O{\mathord {\left(mn^{2}\right)}}$ ( $m\geq n$ )
Determinant	One $n\times n$ matrix	One number	Laplace expansion	$O(n!)$
			Division-free algorithm^[28]	$O{\mathord {\left(n^{4}\right)}}$
			LU decomposition	$O(n^{3})$
			Bareiss algorithm	$O{\mathord {\left(n^{3}\right)}}$
			Fast matrix multiplication^[29]	$O{\mathord {\left(n^{2.373}\right)}}$
Back substitution	Triangular matrix	$n$ solutions	Back substitution^[30]	$O{\mathord {\left(n^{2}\right)}}$

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.^[31]

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 $n$	Set of complex numbers	Fast Fourier transform	$O(n\log n)$

Notes

^ This form of sub-exponential time is valid for all $\varepsilon >0$ . A more precise form of the complexity can be given as $O{\mathord {\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}}.$

References

^ ^a ^b Schönhage, A.; Grotefeld, A.F.W.; Vetter, E. (1994). Fast Algorithms—A Multitape Turing Machine Implementation. BI Wissenschafts-Verlag. ISBN 978-3-411-16891-0. OCLC 897602049.
^ Knuth 1997
^ Harvey, D.; Van Der Hoeven, J. (2021). "Integer multiplication in time O (n log n)" (PDF). Annals of Mathematics. 193 (2): 563–617. doi:10.4007/annals.2021.193.2.4. S2CID 109934776.
^ Klarreich, Erica (December 2019). "Multiplication hits the speed limit". Commun. ACM. 63 (1): 11–13. doi:10.1145/3371387. S2CID 209450552.
^ Christoph Burnikel and Joachim Ziegler Fast Recursive Division Im Stadtwald, D- Saarbrucken 1998.
^ "Fast Euclidean algorithm". PlanetMath.
^ Borwein, J.; Borwein, P. (1987). Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. Wiley. ISBN 978-0-471-83138-9. OCLC 755165897.
^ Chudnovsky, David; Chudnovsky, Gregory (1988). "Approximations and complex multiplication according to Ramanujan". Ramanujan revisited. Academic Press. pp. 375–472.
^ Brent, Richard P. (1975). "Multiple-precision zero-finding methods and the complexity of elementary function evaluation". In Traub, J.F. (ed.). Analytic Computational Complexity. Academic Press. pp. 151–176. arXiv:1004.3412.
^ ^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
^ Sorenson, J. (1994). "Two Fast GCD Algorithms". Journal of Algorithms. 16 (1): 110–144. doi:10.1006/jagm.1994.1006.
^ Crandall, R.; Pomerance, C. (2005). "Algorithm 9.4.7 (Stehlé-Zimmerman binary-recursive-gcd)". Prime Numbers – A Computational Perspective (2nd ed.). Springer. pp. 471–3.
^ 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.
^ Bernstein, D.J. "Faster Algorithms to Find Non-squares Modulo Worst-case Integers".
^ Brent, Richard P.; Zimmermann, Paul (2010). "An $O(M(n)\log n)$ algorithm for the Jacobi symbol". International Algorithmic Number Theory Symposium. Springer. pp. 83–95. arXiv:1004.2091. doi:10.1007/978-3-642-14518-6_10. ISBN 978-3-642-14518-6. S2CID 7632655.
^ Borwein, P. (1985). "On the complexity of calculating factorials". Journal of Algorithms. 6 (3): 376–380. doi:10.1016/0196-6774(85)90006-9.
^ ^a ^b Lenstra jr., H.W.; Pomerance, Carl (2019). "Primality testing with Gaussian periods" (PDF). Journal of the European Mathematical Society. 21 (4): 1229–69. doi:10.4171/JEMS/861.
^ 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. American Mathematical Society. pp. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4. MR 2780010.
^ 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.
^ Pomerance, Carl; Selfridge, John L.; Wagstaff, Jr., Samuel S. (July 1980). "The pseudoprimes to 25·10⁹" (PDF). Mathematics of Computation. 35 (151): 1003–26. doi:10.1090/S0025-5718-1980-0572872-7. JSTOR 2006210.
^ Baillie, Robert; Wagstaff, Jr., Samuel S. (October 1980). "Lucas Pseudoprimes" (PDF). Mathematics of Computation. 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. JSTOR 2006406. MR 0583518.
^ ^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.
^ 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, doi:10.1137/1.9781611976465.32, S2CID 222290442
^ 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
^ Vassilevska Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier (PDF)
^ 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
^ ^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.
^ Rote, G. (2001). "Division-free algorithms for the determinant and the pfaffian: algebraic and combinatorial approaches" (PDF). Computational discrete mathematics. Springer. pp. 119–135. ISBN 3-540-45506-X.
^ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). "Theorem 6.6". The Design and Analysis of Computer Algorithms. Addison-Wesley. p. 241. ISBN 978-0-201-00029-0.
^ Fraleigh, J.B.; Beauregard, R.A. (1987). Linear Algebra (3rd ed.). Addison-Wesley. p. 95. ISBN 978-0-201-15459-7.
^ Cohn, Henry; Kleinberg, Robert; Szegedy, Balazs; Umans, Chris (2005). "Group-theoretic Algorithms for Matrix Multiplication". Proceedings of the 46th Annual Symposium on Foundations of Computer Science. IEEE. pp. 379–388. arXiv:math.GR/0511460. doi:10.1109/SFCS.2005.39. ISBN 0-7695-2468-0. S2CID 6429088.

@@ Line 4: / Line 4: @@
 The following tables list the [[computational complexity]] of various [[algorithm]]s for common [[mathematical operation]]s.
-Here, complexity refers to the [[time complexity]] of performing computations on a [[multitape Turing machine]].<ref name="Schonhage">A. Schönhage, A.F.W. Grotefeld, E. Vetter: ''Fast Algorithms—A Multitape Turing Machine Implementation'', BI Wissenschafts-Verlag, Mannheim, 1994</ref> See [[big O notation]] for an explanation of the notation used.
+Here, complexity refers to the [[time complexity]] of performing computations on a [[multitape Turing machine]].<ref name="Schonhage">{{cite book |first1=A. |last1=Schönhage |first2=A.F.W. |last2=Grotefeld |first3=E. |last3=Vetter |title=Fast Algorithms—A Multitape Turing Machine Implementation |publisher=BI Wissenschafts-Verlag |date=1994 |isbn=978-3-411-16891-0 |pages= |oclc=897602049}}</ref> See [[big O notation]] for an explanation of the notation used.
 Note: Due to the variety of multiplication algorithms, <math>M(n)</math> below stands in for the complexity of the chosen multiplication algorithm.
@@ Line 44: / Line 44: @@
 |<math>O\mathord\left(n^{\frac{\log(2k - 1)}{\log k}}\right)</math>
 |-
-|Mixed-level Toom–Cook (Knuth 4.3.3-T)<ref>D. Knuth. ''[[The Art of Computer Programming]]'', Volume 2. Third Edition, Addison-Wesley 1997.</ref>
+|Mixed-level Toom–Cook (Knuth 4.3.3-T)<ref>{{harvnb|Knuth|1997}}</ref>
 |<math>O\mathord\left(n \, 2^{\sqrt{2 \log n}} \, \log n\right)</math>
 |-
@@ Line 50: / Line 50: @@
 |<math>O\mathord\left(n \log n \log \log n\right)</math>
 |-
-|[[Harvey-Hoeven algorithm]]<ref>David Harvey, Joris van der Hoeven ''[https://hal.archives-ouvertes.fr/hal-02070778/document Integer multiplication in time O (n log n)].'' (2019).</ref><ref>Erica Klarreich. 2019. Multiplication hits the speed limit. Commun. ACM 63, 1 (December 2019), 11–13. {{doi|10.1145/3371387}}</ref>
+|[[Harvey-Hoeven algorithm]]<ref>{{cite journal |last1=Harvey |first1=D. |last2=Van Der Hoeven |first2=J. |title=Integer multiplication in time O (n log n) |journal=Annals of Mathematics |volume=193 |issue=2 |pages=563–617 |date=2021 |doi=10.4007/annals.2021.193.2.4  |s2cid=109934776 |url=https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf}}</ref><ref>{{cite journal |first=Erica |last=Klarreich |title=Multiplication hits the speed limit |journal=Commun. ACM |volume=63 |issue=1 |pages=11–13 |date=December 2019 |doi=10.1145/3371387 |s2cid=209450552 |url=}}</ref>
 |<math>O(n \log n)</math>
 |-
@@ Line 107: / Line 107: @@
 |<math>O\mathord\left(n^{2}\right)</math>
 |-
-|Fast Euclidean algorithm (Lehmer)<ref>{{Cite web|url=http://planetmath.org/fasteuclideanalgorithm|title = Fast Euclidean algorithm}}</ref>
+|Fast Euclidean algorithm (Lehmer)<ref>{{Cite web|url=http://planetmath.org/fasteuclideanalgorithm|title = Fast Euclidean algorithm |work=PlanetMath}}</ref>
 |<math>O(M(n) \log n)</math>
 |}
 == Special functions ==
-Many of the methods in this section are given in Borwein & Borwein.<ref>J. Borwein & P. Borwein. ''Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity''. John Wiley 1987.</ref>
+Many of the methods in this section are given in Borwein & Borwein.<ref>{{cite book |first1=J. |last1=Borwein |first2=P. |last2=Borwein |title=Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity |publisher=Wiley |date=1987 |isbn=978-0-471-83138-9 |oclc=755165897}}</ref>
 === Elementary functions ===
@@ Line 132: / Line 132: @@
 |<math>O\mathord\left(M(n) n^{1/3} (\log n)^2\right)</math>
 |-
-|Taylor series; [[binary splitting]] + [[bit-burst algorithm]]<ref>David and Gregory Chudnovsky. Approximations and complex multiplication according to Ramanujan. ''Ramanujan revisited'', Academic Press, 1988, pp 375–472.</ref>
+|Taylor series; [[binary splitting]] + [[bit-burst algorithm]]<ref>{{cite book |first1=David |last1=Chudnovsky |first2=Gregory |last2=Chudnovsky |chapter=Approximations and complex multiplication according to Ramanujan |chapter-url= |title=Ramanujan revisited |publisher=Academic Press |date=1988 |isbn= |pages=375–472 |url=}}</ref>
 |<math>\exp, \log, \sin, \cos, \arctan</math>
 |<math>O\mathord\left(M(n) (\log n)^2\right)</math>
 |-
-|[[Arithmetic–geometric mean]] iteration<ref>Richard P. Brent, [https://arxiv.org/abs/1004.3412 ''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.</ref>
+|[[Arithmetic–geometric mean]] iteration<ref>{{cite book |arxiv=1004.3412 |first=Richard P. |last=Brent |chapter=Multiple-precision zero-finding methods and the complexity of elementary function evaluation |chapter-url= |editor-first=J.F. |editor-last=Traub |title=Analytic Computational Complexity |publisher=Academic Press |date=1975 |isbn= |pages=151–176 |url=}}</ref>
 |<math>\exp, \log, \sin, \cos, \arctan</math>
 |<math>O(M(n) \log n)</math>
@@ Line 227: / Line 227: @@
 |<math>O\mathord\left(n^2\right)</math>
 |-
-|Left/right ''k''-ary binary GCD algorithm<ref>{{cite journal | author = J. Sorenson. | title = Two Fast GCD Algorithms | journal = Journal of Algorithms | volume = 16 | issue = 1| pages = 110–144 | year = 1994 | doi=10.1006/jagm.1994.1006}}</ref>
+|Left/right ''k''-ary binary GCD algorithm<ref>{{cite journal |first= J. |last=Sorenson | title = Two Fast GCD Algorithms | journal = Journal of Algorithms | volume = 16 | issue = 1| pages = 110–144 | year = 1994 | doi=10.1006/jagm.1994.1006}}</ref>
 |<math>O\mathord\left(\frac{n^{2}}{\log n}\right)</math>
 |-
-|[[Stehlé–Zimmermann algorithm]]<ref>R. Crandall & C. Pomerance. ''Prime Numbers – A Computational Perspective''. Second Edition, Springer 2005.</ref>
+|[[Stehlé–Zimmermann algorithm]]<ref>{{cite book |first1=R. |last1=Crandall |first2=C. |last2=Pomerance |chapter=Algorithm 9.4.7 (Stehlé-Zimmerman binary-recursive-gcd) |chapter-url={{GBurl|ZXjHKPS1LEAC|p=471}} |pages=471–3 |title=Prime Numbers – A Computational Perspective |publisher=Springer |edition=2nd |date=2005 |isbn= }}</ref>
 |<math>O(M(n) \log n)</math>
 |-
@@ Line 239: / Line 239: @@
 | rowspan="2" |Two <math>n</math>-digit integers
 | rowspan="2" |<math>0</math>, <math>-1</math> or <math>1</math>
-|Schönhage controlled Euclidean descent algorithm<ref>{{cite web|url=http://cr.yp.to/papers/nonsquare.ps|title=Faster Algorithms to Find Non-squares Modulo Worst-case Integers|author=Bernstein D J}}</ref>
+|Schönhage controlled Euclidean descent algorithm<ref>{{cite web|url=http://cr.yp.to/papers/nonsquare.ps|title=Faster Algorithms to Find Non-squares Modulo Worst-case Integers|last=Bernstein |first=D.J.}}</ref>
 |<math>O(M(n) \log n)</math>
 |-
-|Stehlé–Zimmermann algorithm<ref>{{cite arXiv|eprint=1004.2091|class=cs.DS|author1=Richard P. Brent|author2=Paul Zimmermann|title=An <math>O(M(n) \log n)</math> algorithm for the Jacobi symbol|year=2010}}</ref>
+|Stehlé–Zimmermann algorithm<ref>{{cite book |arxiv=1004.2091 |first1=Richard P. |last1=Brent |first2=Paul |last2=Zimmermann |chapter=An <math>O(M(n) \log n)</math> algorithm for the Jacobi symbol|year=2010 |title=International Algorithmic Number Theory Symposium |pages=83–95 |publisher=Springer |doi=10.1007/978-3-642-14518-6_10 |chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-14518-6_10 |isbn=978-3-642-14518-6|s2cid=7632655 }}</ref>
 |<math>O(M(n) \log n)</math>
 |-
@@ Line 261: / Line 261: @@
 | rowspan="5" |True or false
 |[[AKS primality test]]
-|<math>O\mathord\left(n^{6+o(1)}\right)</math><ref name="lenstra_pomerance_2005">H. W. Lenstra Jr. and Carl Pomerance, "[http://www.math.dartmouth.edu/~carlp/PDF/complexity12.pdf Primality testing with Gaussian periods]", preliminary version July 20, 2005.</ref><ref name="lenstra_pomerance_2011">H. W. Lenstra jr. and Carl Pomerance, "[http://www.math.dartmouth.edu/~carlp/aks041411.pdf Primality testing with Gaussian periods] {{Webarchive|url=https://web.archive.org/web/20120225052810/http://www.math.dartmouth.edu/~carlp/aks041411.pdf |date=2012-02-25 }}", version of April 12, 2011.</ref><ref name="tao-aks">{{cite book|title=An epsilon of room, II: Pages from year three of a mathematical blog|last=Tao|first=Terence|publisher=American Mathematical Society|year=2010|isbn=978-0-8218-5280-4|series=Graduate Studies in Mathematics|volume=117|location=Providence, RI|pages=82–86|contribution=1.11 The AKS primality test|doi=10.1090/gsm/117|mr=2780010|author-link=Terence Tao|contribution-url=https://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/}}</ref><ref>{{cite web|last1=Lenstra|first1=Jr., H.W.|author1-link=Hendrik Lenstra|last2=Pomerance|first2=Carl|author2-link=Carl Pomerance|date=December 11, 2016|title=Primality testing with Gaussian periods|url=https://math.dartmouth.edu/~carlp/aks111216.pdf}}</ref><br /><math>O(n^{3})</math>, assuming [[Agrawal's conjecture]]
+|<math>O\mathord\left(n^{6+o(1)}\right)</math><ref name=Lenstra19>{{cite journal |first1=H.W. |last1=Lenstra jr. |first2=Carl |last2=Pomerance |author1-link=Hendrik Lenstra |author2-link=Carl Pomerance |title=Primality testing with Gaussian periods |journal=Journal of the European Mathematical Society |year=2019 |volume=21 |issue=4 |pages=1229–69 |doi=10.4171/JEMS/861 |url=http://www.math.dartmouth.edu/~carlp/aks041411.pdf}}</ref><ref name="tao-aks">{{cite book|title=An epsilon of room, II: Pages from year three of a mathematical blog|last=Tao|first=Terence|publisher=American Mathematical Society|year=2010|isbn=978-0-8218-5280-4|series=Graduate Studies in Mathematics|volume=117 |pages=82–86|contribution=1.11 The AKS primality test|doi=10.1090/gsm/117|mr=2780010|author-link=Terence Tao|contribution-url=https://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/}}</ref><ref name=Lenstra19/><br /><math>O(n^{3})</math>, assuming [[Agrawal's conjecture]]
 |-
 |[[Elliptic curve primality proving]]
@@ Line 267: / Line 267: @@
 |-
 |[[Baillie–PSW primality test]]
-|<math>O\mathord\left(n^{2+\varepsilon}\right)</math><ref name="PSW">{{cite journal|author1=Carl Pomerance|author2=John L. Selfridge|author-link2=John L. Selfridge|author3=Samuel S. Wagstaff, Jr.|author-link3=Samuel S. Wagstaff, Jr.|date=July 1980|title=The pseudoprimes to 25·10<sup>9</sup>|url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf|journal=Mathematics of Computation|volume=35|issue=151|pages=1003–1026|doi=10.1090/S0025-5718-1980-0572872-7|jstor=2006210|author-link1=Carl Pomerance|doi-access=free}}</ref><ref name="lpsp">{{cite journal|author1=Robert Baillie|author2=Samuel S. Wagstaff, Jr.|author-link2=Samuel S. Wagstaff, Jr.|date=October 1980|title=Lucas Pseudoprimes|url=http://mpqs.free.fr/LucasPseudoprimes.pdf|journal=Mathematics of Computation|volume=35|issue=152|pages=1391–1417|doi=10.1090/S0025-5718-1980-0583518-6|jstor=2006406|mr=583518|doi-access=free}}</ref>
+|<math>O\mathord\left(n^{2+\varepsilon}\right)</math><ref name="PSW">{{cite journal|first1=Carl |last1=Pomerance|first2=John L. |last2=Selfridge|author-link2=John L. Selfridge|first3=Samuel S. |last3=Wagstaff, Jr.|author-link3=Samuel S. Wagstaff, Jr.|date=July 1980|title=The pseudoprimes to 25·10<sup>9</sup>|url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf|journal=Mathematics of Computation|volume=35|issue=151|pages=1003–26|doi=10.1090/S0025-5718-1980-0572872-7|jstor=2006210|author-link1=Carl Pomerance|doi-access=free}}</ref><ref name="lpsp">{{cite journal|first1=Robert |last1=Baillie|first2=Samuel S. |last2=Wagstaff, Jr.|author-link2=Samuel S. Wagstaff, Jr.|date=October 1980|title=Lucas Pseudoprimes|url=http://mpqs.free.fr/LucasPseudoprimes.pdf|journal=Mathematics of Computation|volume=35|issue=152|pages=1391–1417|doi=10.1090/S0025-5718-1980-0583518-6|jstor=2006406|mr=583518|doi-access=free}}</ref>
 |-
 |[[Miller–Rabin primality test]]
@@ Line 316: / Line 316: @@
  | first2=Virginia Vassilevska
  | contribution=A Refined Laser Method and Faster Matrix Multiplication
- | year = 2020
+ | year = 2020 |doi=10.1137/1.9781611976465.32
  | arxiv=2010.05846
  | title = 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
+ | s2cid=222290442
  |url=https://www.siam.org/conferences/cm/program/accepted-papers/soda21-accepted-papers
 }}</ref><ref>{{Citation | last1=Davie | first1=A.M. | last2=Stothers | first2=A.J. | title=Improved bound for complexity of matrix multiplication|journal=Proceedings of the Royal Society of Edinburgh|volume=143A| issue=2 |pages=351–370|year=2013|doi=10.1017/S0308210511001648| s2cid=113401430 }}</ref><ref>{{Citation | last1=Vassilevska Williams | first1=Virginia|author-link= Virginia Vassilevska Williams | title=Breaking the Coppersmith-Winograd barrier | url=http://theory.stanford.edu/~virgi/matrixmult-f.pdf | year=2011}}</ref><ref>{{Citation | last1=Le Gall | first1=François | contribution=Powers of tensors and fast matrix multiplication | year = 2014 | arxiv=1401.7714 | title = Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation - ISSAC '14| bibcode=2014arXiv1401.7714L | title-link=ISSAC | page=23 | doi=10.1145/2608628.2627493 | isbn=9781450325011 | s2cid=353236 }}</ref> ([[galactic algorithm]]s)
@@ Line 366: / Line 367: @@
 |<math>O(n!)</math>
 |-
-|Division-free algorithm<ref>http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf {{Bare URL PDF|date=March 2022}}</ref>
+|Division-free algorithm<ref>{{cite book |first=G. |last=Rote |chapter=Division-free algorithms for the determinant and the pfaffian: algebraic and combinatorial approaches |chapter-url=http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf |title=Computational discrete mathematics  |publisher=Springer |date=2001 |isbn=3-540-45506-X |pages=119–135 |url=}}</ref>
 |<math>O\mathord\left(n^{4}\right)</math>
 |-
@@ Line 375: / Line 376: @@
 |<math>O\mathord\left(n^3\right)</math>
 |-
-|Fast matrix multiplication<ref>{{citation|at=Theorem 6.6, p.&nbsp;241|title=The Design and Analysis of Computer Algorithms|first1=Alfred V.|last1=Aho|author1-link=Alfred Aho|first2=John E.|last2=Hopcroft|author2-link=John Hopcroft|first3=Jeffrey D.|last3=Ullman|author3-link=Jeffrey Ullman|publisher=Addison-Wesley|year=1974}}</ref>
+|Fast matrix multiplication<ref>{{cite book |chapter=Theorem 6.6 |page=241|title=The Design and Analysis of Computer Algorithms|first1=Alfred V.|last1=Aho|author1-link=Alfred Aho|first2=John E.|last2=Hopcroft|author2-link=John Hopcroft|first3=Jeffrey D.|last3=Ullman|author3-link=Jeffrey Ullman|publisher=Addison-Wesley|year=1974 |isbn=978-0-201-00029-0}}</ref>
 |<math>O\mathord\left(n^{2.373}\right)</math>
 |-
@@ Line 382: / Line 383: @@
 |[[Triangular matrix]]
 |<math>n</math> solutions
-|Back substitution<ref>J. B. Fraleigh and R. A. Beauregard, "Linear Algebra," Addison-Wesley Publishing Company, 1987, p 95.</ref>
+|Back substitution<ref>{{cite book |first1=J.B. |last1=Fraleigh |first2=R.A. |last2=Beauregard |title=Linear Algebra |publisher=Addison-Wesley |edition=3rd |date=1987 |isbn=978-0-201-15459-7 |pages=95 |url=}}</ref>
 |<math>O\mathord\left(n^2\right)</math>
 |}
-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.<ref>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.</ref>
+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.<ref>{{cite book |first1=Henry |last1=Cohn |first2=Robert |last2=Kleinberg |first3=Balazs |last3=Szegedy |first4=Chris |last4=Umans |arxiv=math.GR/0511460 |chapter=Group-theoretic Algorithms for Matrix Multiplication |chapter-url= |title=Proceedings of the 46th Annual Symposium on Foundations of Computer Science |year=2005 |publisher=IEEE |isbn=0-7695-2468-0 |pages=379–388 |doi=10.1109/SFCS.2005.39|s2cid=6429088 }}</ref>
 == Transforms ==
@@ Line 411: / Line 412: @@
 == Further reading ==
+{{refbegin}}
 * {{cite book |last1=Brent |first1=Richard P. |author-link1=Richard P. Brent |last2=Zimmermann |first2=Paul |author-link2=Paul Zimmermann (mathematician) |title=Modern Computer Arithmetic |year=2010 |publisher=Cambridge University Press |isbn=978-0-521-19469-3}}
-* {{cite book |last1=Knuth |first1=Donald Ervin |author-link=Donald Knuth |title=The Art of Computer Programming. Volume 2: Seminumerical Algorithms|year=1997| edition=3rd |publisher=Addison-Wesley |isbn=978-0-201-89684-8}}
+* {{cite book |last1=Knuth |first1=Donald Ervin |author-link=Donald Knuth |series=[[The Art of Computer Programming]] |volume=2 |title=Seminumerical Algorithms|year=1997| edition=3rd |publisher=Addison-Wesley |isbn=978-0-201-89684-8}}
+{{refend}}
 [[Category:Computer arithmetic algorithms]]