Algoritmo de Fürer
El algoritmo de Fürer es un algoritmo de multiplicación de enteros para enteros extremadamente grandes con muy baja complejidad asintótica . 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 que su predecesor (algoritmo Schönhage-Strassen) al ser analizado en una máquina Turing multicinta.[2]
Contexto
[editar]El algoritmo Schönhage – Strassen utiliza la transformación rápida de Fourier (FFT) para calcular productos enteros en tiempo y 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 usar para multiplicar enteros de longitud a tiempo donde log* n es el logaritmo iterado. La diferencia entre los términos y , desde el punto de vista de la complejidad, es la ventaja asintótica en el algoritmo de Fürer para enteros mayores que . Sin embargo, la diferencia entre estos términos para valores realistas de es muy pequeño.[1]
Algoritmos mejorados
[editar]En 2008, Lüders et al dieron un algoritmo similar que se basa en la aritmética modular en lugar de la 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, 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 de . También propusieron una variante de su algoritmo que logra pero cuya validez se basa en conjeturas estándar sobre la distribución de 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 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 utiliza 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 short lattice 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 muy buscado algoritmo de multiplicación de enteros que se supone que es asintóticamente óptimo.[11][12] Porque Schönhage y Strassen predijeron que n log (n) es el "mejor resultado posible", dijo Harvey: "... se espera que nuestro trabajo sea el final del camino para este problema, aunque todavía no sabemos cómo demostrarlo rigurosamente".[13]
Referencias
[editar]- ↑ a b M. Fürer (2007). "Faster Integer Multiplication" Proceedings of the 39th annual ACM Symposium on Theory of Computing (STOC), 55–67, San Diego, CA, June 11–13, 2007, and SIAM Journal on Computing, Vol. 39 Issue 3, 979–1005, 2009.
- ↑ Schönhage, A.; Strassen, V. (1971). «Schnelle Multiplikation großer Zahlen» [Fast Multiplication of Large Numbers]. Computing (en alemán) 7 (3–4): 281-292. doi:10.1007/BF02242355.
- ↑ A. De, C. Saha, P. Kurur and R. Saptharishi (2008). "Fast integer multiplication using modular arithmetic" Proceedings of the 40th annual ACM Symposium on Theory of Computing (STOC), 499–506, New York, NY, 2008, and SIAM Journal on Computing, Vol. 42 Issue 2, 685–699, 2013. arΧiv:0801.1416
- ↑ . International Symposium on Symbolic and Algebraic Computation (pdf. 2015. pp. 267-274. )
- ↑ D. Harvey, J. van der Hoeven and G. Lecerf (2015). "Even faster integer multiplication", February 2015. arΧiv:1407.3360
- ↑ Covanov, S.; Thomé, E. (2015). Fast Arithmetic for Faster Integer Multiplication. Published asCovanov y Thomé (2019).
- ↑ S. Covanov and E. Thomé (2014). "Efficient implementation of an algorithm multiplying big numbers", Internal research report, Polytechnics School, France, July 2014.
- ↑ S. Covanov and M. Moreno Mazza (2015). "Putting Fürer algorithm into practice", Master research report, Polytechnics School, France, January 2015.
- ↑ Covanov, Svyatoslav; Thomé, Emmanuel (2019). «Fast Integer Multiplication Using Generalized Fermat Primes». Math. Comp. 88: 1449-1477. arXiv:1502.02800. doi:10.1090/mcom/3367.
- ↑ D. Harvey and J. van der Hoeven (2018). "Faster integer multiplication using short lattice vectors", February 2018. arΧiv:1802.07932
- ↑ Harvey, David; Van Der Hoeven, Joris (12 de abril de 2019). Integer multiplication in time O(n log n).
- ↑ Hartnett, Kevin (14 de abril de 2019). «Mathematicians Discover the Perfect Way to Multiply». ISSN 1059-1028. Consultado el 15 de abril de 2019.
- ↑ Gilbert, Lachlan (4 de abril de 2019). «Maths whiz solves 48-year-old multiplication problem». UNSW. Consultado el 18 de abril de 2019.