El algoritmo de Fürer es un algoritmo de multiplicación de enteros para enteros extremadamente grandes con una complejidad asintótica muy baja . Fue publicado en 2007 por el matemático suizo Martin Fürer de la Universidad Estatal de Pensilvania [1] como un algoritmo asintóticamente más rápido cuando se analiza en una máquina de Turing de varias cintas que su predecesor, el algoritmo Schönhage-Strassen . [2]
Fondo
El algoritmo de Schönhage-Strassen utiliza la transformada rápida de Fourier (FFT) para calcular productos enteros en el tiempoy sus autores, Arnold Schönhage y Volker Strassen , conjeturan un límite inferior de. El algoritmo de Fürer reduce la brecha entre estos dos límites. Se puede utilizar para multiplicar enteros de longitud. a tiempo donde log * n es el logaritmo iterado . La diferencia entre el y términos, desde el punto de vista de la complejidad, es asintóticamente en la ventaja del algoritmo de Fürer para enteros mayores que . Sin embargo, la diferencia entre estos términos para valores realistas dees muy pequeño. [1]
Algoritmos mejorados
En 2008, De et al dieron un algoritmo similar que se basa en aritmética modular en lugar de aritmética compleja para lograr, de hecho, el mismo tiempo de ejecución. [3] Se ha estimado que se vuelve más rápido que Schönhage-Strassen para entradas que exceden una longitud de. [4]
En 2015, Harvey, Joris van der Hoeven y Lecerf [5] dieron un nuevo algoritmo que logra un tiempo de ejecución de haciendo explícita la constante implícita en el exponente. También propusieron una variante de su algoritmo que lograpero cuya validez se basa en conjeturas estándar sobre la distribución de los números primos de Mersenne .
En 2015, Covanov y Thomé proporcionaron otra modificación del algoritmo de Fürer que logra el mismo tiempo de ejecución. [6] Sin embargo, sigue siendo tan poco práctico como todas las demás implementaciones de este algoritmo. [7] [8]
En 2016, Covanov y Thomé propusieron un algoritmo de multiplicación de enteros basado en una generalización de los números primos de Fermat que, conjeturalmente, logra un límite de complejidad de. Esto coincide con el resultado condicional de 2015 de Harvey, van der Hoeven y Lecerf, pero usa un algoritmo diferente y se basa en una conjetura diferente. [9]
En 2018, Harvey y van der Hoeven utilizaron un enfoque basado en la existencia de vectores de celosía cortos garantizados por el teorema de Minkowski para demostrar un límite de complejidad incondicional de. [10]
En marzo de 2019, Harvey y van der Hoeven publicaron un codiciado algoritmo de multiplicación de enteros, que se supone que es asintóticamente óptimo. [11] [12] Debido a que Schönhage y Strassen predijeron que n log ( n ) es el 'mejor resultado posible', Harvey dijo: “... se espera que nuestro trabajo sea el final del camino para este problema, aunque no lo hacemos ' Todavía no sé cómo demostrar esto rigurosamente ". [13]
Ver también
Referencias
- ↑ a b M. Fürer (2007). " Más rápido multiplicación de enteros " Actas de la 39ª anual Simposio ACM sobre Teoría de la Computación (COTS), 55-67, San Diego, CA, 11-13 de junio de 2007, y SIAM Journal on Computing , vol. 39 Edición 3, 979–1005, 2009.
- ^ Schönhage, A .; Strassen, V. (1971). "Schnelle Multiplikation großer Zahlen" [Multiplicación rápida de números grandes]. Computación (en alemán). 7 (3–4): 281–292. doi : 10.1007 / BF02242355 .
- ^ A. De, C. Saha, P. Kurur y R. Saptharishi (2008). "Multiplicación rápida de enteros usando aritmética modular" Actas del 40º Simposio anual ACM sobre Teoría de la Computación (STOC), 499–506, Nueva York, NY, 2008, y SIAM Journal on Computing , vol. 42 Edición 2, 685–699, 2013. arXiv : 0801.1416
- ^ Lüders, Christoph (2015). Implementación del algoritmo DKSS para la multiplicación de números grandes (pdf) . Simposio Internacional de Computación Simbólica y Algebraica. págs. 267-274.
- ^ D. Harvey, J. van der Hoeven y G. Lecerf (2015). "Multiplicación de enteros aún más rápida", febrero de 2015. arXiv : 1407.3360
- ^ Covanov, S .; Thomé, E. (2015). "Aritmética rápida para una multiplicación de enteros más rápida". arXiv : 1502.02800v1 . Cite journal requiere
|journal=
( ayuda )Publicado como Covanov & Thomé (2019) . - ^ S. Covanov y E. Thomé (2014). "Implementación eficiente de un algoritmo multiplicando números grandes", Informe de investigación interna, Escuela Politécnica, Francia, julio de 2014.
- ^ S. Covanov y M. Moreno Mazza (2015). "Poner en práctica el algoritmo de Fürer", Informe de investigación de maestría, Escuela Politécnica, Francia, enero de 2015.
- ^ Covanov, Svyatoslav; Thomé, Emmanuel (2019). "Multiplicación rápida de enteros utilizando primas Fermat generalizadas". Matemáticas. Comp. 88 : 1449-1477. arXiv : 1502.02800 . doi : 10.1090 / mcom / 3367 .
- ^ D. Harvey y J. van der Hoeven (2018). "Multiplicación de enteros más rápida con vectores de celosía cortos", febrero de 2018. arXiv : 1802.07932
- ^ Harvey, David; Van Der Hoeven, Joris (12 de abril de 2019). Multiplicación de enteros en el tiempo O (n log n) .
- ^ Hartnett, Kevin (14 de abril de 2019). "Los matemáticos descubren la manera perfecta de multiplicar" . Cableado . ISSN 1059-1028 . Consultado el 15 de abril de 2019 .
- ^ Gilbert, Lachlan (4 de abril de 2019). "El genio de las matemáticas resuelve un problema de multiplicación de 48 años" . UNSW . Consultado el 18 de abril de 2019 .