Las siguientes tablas enumeran la complejidad computacional de varios algoritmos para operaciones matemáticas comunes .
Aquí, la complejidad se refiere a la complejidad temporal de realizar cálculos en una máquina de Turing de varias cintas . [1] Consulte la notación O grande para obtener una explicación de la notación utilizada.
Nota: Debido a la variedad de algoritmos de multiplicación, a continuación representa la complejidad del algoritmo de multiplicación elegido.
Funciones aritméticas
Operación | Aporte | Producción | Algoritmo | Complejidad |
---|---|---|---|---|
Adición | Dos -números de dígitos, y | Uno -dígito | Adición de libros escolares con llevar | |
Sustracción | Dos -números de dígitos, y | Uno -dígito | Resta de libros escolares con préstamo | |
Multiplicación | Dos -números de dígitos | Uno -dígito | Libro de texto multiplicación larga | |
Algoritmo de Karatsuba | ||||
Multiplicación de Toom-Cook de 3 vías | ||||
-way Toom-Cook multiplicación | ||||
Toom-Cook de nivel mixto (Knuth 4.3.3-T) [2] | ||||
Algoritmo de Schönhage-Strassen | ||||
Algoritmo de Fürer [3] | ||||
Algoritmo de Harvey-Hoeven [4] [5] | ||||
División | Dos -números de dígitos | Uno -dígito | División larga del libro escolar | |
División Burnikel-Ziegler Divide-and-Conquer [6] | ||||
División de Newton-Raphson | ||||
Raíz cuadrada | Uno -dígito | Uno -dígito | Método de Newton | |
Exponenciación modular | Dos -dígitos enteros y un exponente de bits | Uno -digit entero | Multiplicación y reducción repetidas | |
Exponenciación por cuadratura | ||||
Exponenciación con reducción de Montgomery |
Funciones algebraicas
Operación | Aporte | Producción | Algoritmo | Complejidad |
---|---|---|---|---|
Evaluación polinomial | Un polinomio de grado con coeficientes de tamaño fijo | Un número de tamaño fijo | Evaluación directa | |
El método de Horner | ||||
Polinomio mcd (más o ) | Dos polinomios de grado con coeficientes enteros de tamaño fijo | Un polinomio de grado como máximo | Algoritmo euclidiano | |
Algoritmo euclidiano rápido (Lehmer) [7] |
Funciones especiales
Muchos de los métodos de esta sección se dan en Borwein & Borwein. [8]
Funciones elementales
Las funciones elementales se construyen componiendo operaciones aritméticas, la función exponencial (), el logaritmo natural (), funciones trigonométricas (), y sus inversas. La complejidad de una función elemental es equivalente a la de su inversa, ya que todas las funciones elementales son analíticas y, por tanto, invertibles mediante el método de Newton. En particular, si alguno o en el dominio complejo se puede calcular con cierta complejidad, entonces esa complejidad es alcanzable para todas las demás funciones elementales.
Abajo, el tamaño se refiere al número de dígitos de precisión con los que se evaluará la función.
Algoritmo | Aplicabilidad | Complejidad |
---|---|---|
Serie de Taylor ; reducción repetida de argumentos (p. ej.) y suma directa | ||
Serie de Taylor; Aceleración basada en FFT | ||
Serie de Taylor; algoritmo de división binaria + ráfaga de bits [9] | ||
Aritmética-media geométrica iteración [10] |
No se sabe si es la complejidad óptima para funciones elementales. El límite inferior más conocido es el límite trivial..
Funciones no elementales
Función | Aporte | Algoritmo | Complejidad |
---|---|---|---|
Función gamma | -dígito | Aproximación en serie de la función gamma incompleta | |
Número racional fijo | Serie hipergeométrica | ||
, por entero. | Aritmética-media geométrica iteración | ||
Función hipergeométrica | -dígito | (Como se describe en Borwein & Borwein) | |
Número racional fijo | Serie hipergeométrica |
Constantes matematicas
Esta tabla da la complejidad de calcular aproximaciones a las constantes dadas para dígitos correctos.
Constante | Algoritmo | Complejidad |
---|---|---|
Proporción de oro , | Método de Newton | |
Raíz cuadrada de 2 , | Método de Newton | |
Número de Euler , | División binaria de la serie de Taylor para la función exponencial | |
Inversión de Newton del logaritmo natural | ||
Pi , | División binaria de la serie arctan en la fórmula de Machin | [11] |
Algoritmo de Gauss-Legendre | [11] | |
Constante de Euler , | Método de Sweeney (aproximación en términos de la integral exponencial ) |
Teoría de los números
Los algoritmos para cálculos teóricos numéricos se estudian en teoría numérica computacional .
Operación | Aporte | Producción | Algoritmo | Complejidad |
---|---|---|---|---|
Máximo común divisor | Dos -dígitos enteros | Un entero con como máximo digitos | Algoritmo euclidiano | |
Algoritmo binario GCD | ||||
Izquierda / derecha k ary binario GCD algoritmo [12] | ||||
Algoritmo de Stehlé-Zimmermann [13] | ||||
Algoritmo de descenso euclidiano controlado por Schönhage [14] | ||||
Símbolo de jacobi | Dos -dígitos enteros | , o | Algoritmo de descenso euclidiano controlado por Schönhage [15] | |
Algoritmo de Stehlé-Zimmermann [16] | ||||
Factorial | Un entero positivo menor que | Uno -digit entero | Multiplicación de abajo hacia arriba | |
División binaria | ||||
Exponenciación de los factores primos de | , [17] [1] | |||
Prueba de primordialidad | A -digit entero | Verdadero o falso | Prueba de primalidad de AKS | [18] [19] o, [20] [21] , asumiendo la conjetura de Agrawal |
Demostración de primalidad de curva elíptica | heurísticamente [22] | |||
Prueba de primalidad de Baillie-PSW | [23] [24] | |||
Prueba de primalidad de Miller-Rabin | [25] | |||
Prueba de primordialidad de Solovay-Strassen | [25] | |||
Factorización de enteros | A -bit entero de entrada | Un conjunto de factores | Tamiz de campo de número general | [nb 1] |
Algoritmo de Shor | , en una computadora cuántica |
Álgebra de matrices
Las siguientes cifras de complejidad asumen que la aritmética con elementos individuales tiene complejidad O (1), como es el caso de la aritmética de punto flotante de precisión fija o las operaciones en un campo finito .
Operación | Aporte | Producción | Algoritmo | Complejidad |
---|---|---|---|---|
Multiplicación de matrices | Dos matrices | Uno matriz | Multiplicación de matrices de libros escolares | |
Algoritmo de Strassen | ||||
Algoritmo de calderero-Winograd ( algoritmo galáctico ) | ||||
Algoritmos optimizados similares a CW [26] [27] [28] [29] ( algoritmos galácticos ) | ||||
Multiplicación de matrices | Uno matriz y uno matriz | Uno matriz | Multiplicación de matrices de libros escolares | |
Multiplicación de matrices | Uno matriz y uno matriz, para algunos | Uno matriz | Algoritmos dados en [30] | , donde los límites superiores en se dan en [30] |
Inversión de matriz * | Uno matriz | Uno matriz | Eliminación Gauss-Jordan | |
Algoritmo de Strassen | ||||
Algoritmo de calderero-Winograd | ||||
Algoritmos optimizados similares a CW | ||||
Valor singular de descomposición | Uno matriz | Uno matriz, unomatriz y uno matriz | Algoritmo de bidiagonalización y QR | () |
Uno matriz, unomatriz y uno matriz | Algoritmo de bidiagonalización y QR | () | ||
Determinante | Uno matriz | Un número | Expansión de Laplace | |
Algoritmo sin división [31] | ||||
Descomposición LU | ||||
Algoritmo de bareiss | ||||
Multiplicación rápida de matrices [32] | ||||
Sustitución trasera | Matriz triangular | soluciones | Sustitución hacia atrás [33] |
En 2005, Henry Cohn , Robert Kleinberg , Balázs Szegedy y Chris Umans demostraron que cualquiera de dos conjeturas diferentes implicaría que el exponente de la multiplicación de matrices es 2. [34]
Transforma
Los algoritmos para calcular transformaciones de funciones (en particular transformaciones integrales ) se utilizan ampliamente en todas las áreas de las matemáticas, en particular el análisis y el procesamiento de señales .
Operación | Aporte | Producción | Algoritmo | Complejidad |
---|---|---|---|---|
Transformada discreta de Fourier | Secuencia de datos finita de tamaño | Conjunto de números complejos | Transformada rápida de Fourier |
Notas
- ^ Esta forma de tiempo sub-exponencial es válida para todos. Se puede dar una forma más precisa de la complejidad como
Referencias
- ^ a b A. Schönhage, AFW Grotefeld, E. Vetter: Algoritmos rápidos : una implementación de máquina de Turing de varias cintas , BI Wissenschafts-Verlag, Mannheim, 1994
- ^ D. Knuth. El arte de la programación informática , volumen 2. Tercera edición, Addison-Wesley 1997.
- ^ Martín Fürer. Multiplicación de enteros más rápida [https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf Archivado el 25 de abril de 2013 en Wayback Machine . Actas del 39º Simposio Anual de ACM sobre Teoría de la Computación , San Diego, California, EE. UU., 11 al 13 de junio de 2007, págs. 55–67.
- ^ David Harvey, Joris van der Hoeven Multiplicación de enteros en el tiempo O (n log n) . (2019).
- ^ Erica Klarreich. 2019. La multiplicación llega al límite de velocidad. Comun. ACM 63, 1 (diciembre de 2019), 11-13. doi : 10.1145 / 3371387
- ^ Christoph Burnikel y Joachim Ziegler División recursiva rápida Im Stadtwald, D- Saarbrucken 1998.
- ^ http://planetmath.org/fasteuclideanalgorithm
- ^ J. Borwein y P. Borwein. Pi y la AGM: un estudio en teoría analítica de números y complejidad computacional . John Wiley 1987.
- ^ David y Gregory Chudnovsky. Aproximaciones y multiplicaciones complejas según Ramanujan. Ramanujan revisitado , Academic Press, 1988, págs. 375–472.
- ^ Richard P. Brent, Métodos de búsqueda de cero de precisión múltiple y la complejidad de la evaluación de funciones elementales , en: Complejidad Computacional Analítica (JF Traub, ed.), Academic Press, Nueva York, 1975, 151-176.
- ^ a b Richard P. Brent (2020), The Borwein Brothers, Pi and the AGM , Springer Proceedings in Mathematics & Statistics, 313 , arXiv : 1802.07558 , doi : 10.1007 / 978-3-030-36568-4 , ISBN 978-3-030-36567-7, S2CID 214742997
- ^ J. Sorenson. (1994). "Dos algoritmos GCD rápidos". Revista de algoritmos . 16 (1): 110-144. doi : 10.1006 / jagm.1994.1006 .
- ^ R. Crandall y C. Pomerance. Números primos: una perspectiva computacional . Segunda edición, Springer 2005.
- ^ Möller N (2008). "Sobre el algoritmo de Schönhage y el cálculo de gcd de enteros subcuadráticos" (PDF) . Matemáticas de la Computación . 77 (261): 589–607. Código Bibliográfico : 2008MaCom..77..589M . doi : 10.1090 / S0025-5718-07-02017-0 .
- ^ Bernstein D J. "Algoritmos más rápidos para encontrar números enteros en el peor de los casos de módulo que no son cuadrados" .
- ^ Richard P. Brent; Paul Zimmermann (2010). "Unalgoritmo para el símbolo de Jacobi ". arXiv : 1004.2091 [ cs.DS ].
- ^ Borwein, P. (1985). "Sobre la complejidad del cálculo de factoriales". Revista de algoritmos . 6 (3): 376–380. doi : 10.1016 / 0196-6774 (85) 90006-9 .
- ^ HW Lenstra Jr. y Carl Pomerance, " Prueba de primordialidad con períodos gaussianos ", versión preliminar 20 de julio de 2005.
- ^ HW Lenstra jr. y Carl Pomerance, " Pruebas de primordialidad con períodos gaussianos. Archivado el 25 de febrero de 2012en la Wayback Machine ", versión del 12 de abril de 2011.
- ^ Tao, Terence (2010). "1.11 La prueba de primalidad de AKS" . Un épsilon de habitación, II: páginas del tercer año de un blog de matemáticas . Estudios de Posgrado en Matemáticas. 117 . Providence, RI: Sociedad Matemática Estadounidense. págs. 82–86. doi : 10.1090 / gsm / 117 . ISBN 978-0-8218-5280-4. Señor 2780010 .
- ^ Lenstra, Jr., HW ; Pomerance, Carl (11 de diciembre de 2016). "Prueba de primalidad con períodos gaussianos" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Morain, F. (2007). "Implementación de la versión asintóticamente rápida del algoritmo de prueba de primalidad de curva elíptica". Matemáticas de la Computación . 76 (257): 493–505. arXiv : matemáticas / 0502097 . Código bibliográfico : 2007MaCom..76..493M . doi : 10.1090 / S0025-5718-06-01890-4 . Señor 2261033 . S2CID 133193 .
- ^ Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff, Jr. (julio de 1980). "Los pseudoprimes a 25 · 10 9 " (PDF) . Matemáticas de la Computación . 35 (151): 1003–1026. doi : 10.1090 / S0025-5718-1980-0572872-7 . JSTOR 2006210 .
- ^ Robert Baillie; Samuel S. Wagstaff, Jr. (octubre de 1980). "Lucas Pseudoprimes" (PDF) . Matemáticas de la Computación . 35 (152): 1391-1417. doi : 10.1090 / S0025-5718-1980-0583518-6 . JSTOR 2006406 . Señor 0583518 .
- ^ a b Monier, Louis (1980). "Evaluación y comparación de dos algoritmos de prueba de primalidad probabilística eficientes". Informática Teórica . 12 (1): 97–108. doi : 10.1016 / 0304-3975 (80) 90007-9 . Señor 0582244 .
- ^ Alman, Josh; Williams, Virginia Vassilevska (2020), "Un método láser refinado y una multiplicación de matrices más rápida", 32 ° Simposio anual ACM-SIAM sobre algoritmos discretos (SODA 2021) , arXiv : 2010.05846
- ^ Davie, AM; Stothers, AJ (2013), "Límite mejorado para la complejidad de la multiplicación de matrices", Actas de la Royal Society of Edinburgh , 143A (2): 351–370, doi : 10.1017 / S0308210511001648 , S2CID 113401430
- ^ Vassilevska Williams, Virginia (2011), Rompiendo la barrera Coppersmith-Winograd (PDF)
- ^ Le Gall, François (2014), "Poderes de tensores y multiplicación rápida de matrices", Actas del 39º Simposio Internacional sobre Computación Simbólica y Algebraica (ISSAC 2014) , arXiv : 1401.7714 , Bibcode : 2014arXiv1401.7714L
- ^ a b Le Gall, François; Urrutia, Floren (2018). "Multiplicación de matriz rectangular mejorada utilizando poderes del tensor de calderero-Winograd". En Czumaj, Artur (ed.). Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos . Sociedad de Matemática Industrial y Aplicada (SIAM). doi : 10.1137 / 1.9781611975031.67 . ISBN 978-1-61197-503-1. S2CID 33396059 .
- ^ http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf
- ^ Aho, Alfred V .; Hopcroft, John E .; Ullman, Jeffrey D. (1974), El diseño y análisis de algoritmos informáticos , Addison-Wesley, Teorema 6.6, p. 241
- ^ JB Fraleigh y RA Beauregard, "Álgebra lineal", Addison-Wesley Publishing Company, 1987, p 95.
- ^ Henry Cohn, Robert Kleinberg, Balazs Szegedy y Chris Umans. Algoritmos teóricos de grupos para la multiplicación de matrices. arXiv : matemáticas.GR / 0511460 . Actas del 46º Simposio Anual sobre Fundamentos de las Ciencias de la Computación , 23-25 de octubre de 2005, Pittsburgh, PA, IEEE Computer Society, págs. 379–388.
Otras lecturas
- Brent, Richard P .; Zimmermann, Paul (2010). Aritmética informática moderna . Prensa de la Universidad de Cambridge. ISBN 978-0-521-19469-3.
- Knuth, Donald Ervin (1997). El arte de la programación informática. Volumen 2: Algoritmos seminuméricos (3ª ed.). Addison-Wesley. ISBN 978-0-201-89684-8.