Ver el código de «Algoritmo de Fürer»

'''El algoritmo de Fürer''' es un [[Algoritmo de multiplicación|algoritmo de multiplicación de enteros]] para enteros extremadamente grandes con muy baja [[Teoría de la complejidad computacional|complejidad asintótica]] . Fue publicado en 2007 por el matemático suizo [[ Martin Fürer |Martin Fürer]] de la Universidad Estatal de Pensilvania<ref name="fürer_1">M. Fürer (2007). "[https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf 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.</ref> como un algoritmo asintóticamente más rápido que su predecesor ([[Algoritmo de Schönhage-Strassen|algoritmo Schönhage-Strassen]]) al ser analizado en una máquina Turing multicinta.<ref>{{Cita publicación|título=Schnelle Multiplikation großer Zahlen|apellidos=Schönhage|nombre=A.|apellidos2=Strassen|nombre2=V.|publicación=[[Computing (journal)|Computing]]|volumen=7|número=3–4|páginas=281–292|idioma=de|títulotrad=Fast Multiplication of Large Numbers|doi=10.1007/BF02242355|año=1971}}</ref> 

== Contexto ==
El algoritmo Schönhage – Strassen utiliza la [[Transformada rápida de Fourier|transformación rápida de Fourier]] (FFT) para calcular productos enteros en tiempo <math>O (n \log n \cdot \log \log n)</math> y sus autores, Arnold Schönhage y [[Volker Strassen]], conjeturan un límite inferior de {{Nowrap|<math>\Omega(n \log n)</math>.}} El algoritmo de Fürer reduce la brecha entre estos dos límites. Se puede usar para multiplicar enteros de longitud <math>n</math> a tiempo <math style="vertical-align:-15%">O \left(n \log n\ \cdot 2^{O(\log^* n)} \right)</math> donde log* n  es el [[logaritmo iterado]]. La diferencia entre los términos <math>\log\log n</math> y <math>2^{\log^* n}</math>, desde el punto de vista de la complejidad, es la ventaja asintótica en el algoritmo de Fürer para enteros mayores que <math>2^{2^{64}}</math>. Sin embargo, la diferencia entre estos términos para valores realistas de <math>n</math> es muy pequeño.<ref name="fürer_1">M. Fürer (2007). "[https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf 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.</ref> 

== Algoritmos mejorados ==
En 2008, Lüders ''et al'' dieron un algoritmo similar que se basa en [[Aritmética modular|la aritmética modular]] en lugar de la aritmética compleja para lograr, de hecho, el mismo tiempo de ejecución.<ref>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. {{Arxiv|0801.1416}}</ref> Se ha estimado que se vuelve más rápido que Schönhage-Strassen para entradas que exceden una longitud de <math>10^{10^{4796}}</math>.<ref>{{Cita conferencia|formato=pdf|conferencia=International Symposium on Symbolic and Algebraic Computation|páginas=267-274|fecha=2015}}</ref> 

En 2015, Harvey, van der Hoeven y Lecerf<ref>D. Harvey, J. van der Hoeven and G. Lecerf (2015). "Even faster integer multiplication", February 2015. {{Arxiv|1407.3360}}</ref> dieron un nuevo algoritmo que logra un tiempo de ejecución de <math>O(n\log n \cdot 2^{3\log^* n})</math> haciendo explícita la constante implícita en el exponente de <math>O(\log^* n)</math>. También propusieron una variante de su algoritmo que logra <math>O(n\log n \cdot 2^{2\log^* n})</math> pero cuya validez se basa en conjeturas estándar sobre la distribución de [[Número primo de Mersenne|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.<ref>{{Cita publicación|título=Fast Arithmetic for Faster Integer Multiplication|apellidos=Covanov|nombre=S.|apellidos2=Thomé|nombre2=E.|año=2015}} Published as{{Harvtxt|Covanov|Thomé|2019}}.</ref> Sin embargo, sigue siendo tan poco práctico como todas las demás implementaciones de este algoritmo.<ref>S. Covanov and E. Thomé (2014). "Efficient implementation of an algorithm multiplying big numbers", Internal research report, Polytechnics School, France, July 2014.</ref><ref>S. Covanov and M. Moreno Mazza (2015). "Putting Fürer algorithm into practice", Master research report, Polytechnics School, France, January 2015.</ref> 

En 2016, Covanov y Thomé propusieron un algoritmo de multiplicación de enteros basado en una generalización de [[Número de Fermat|números primos de Fermat]] que conjeturalmente logra un límite de complejidad de <math>O(n\log n \cdot 2^{2\log^* n})</math>. 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.<ref>{{Cita publicación|título=Fast Integer Multiplication Using Generalized Fermat Primes|apellidos=Covanov|nombre=Svyatoslav|apellidos2=Thomé|nombre2=Emmanuel|publicación=[[Mathematics of Computation|Math. Comp.]]|volumen=88|número=|páginas=1449–1477|doi=10.1090/mcom/3367|ref=harv|año=2019|arxiv=1502.02800}}</ref> 

En 2018, Harvey y van der Hoeven utilizaron un enfoque basado en la existencia de vectores ''short lattice'' garantizados por [[Teorema de Minkowski|el teorema de Minkowski]] para demostrar un límite de complejidad incondicional de <math>O(n\log n \cdot 2^{2\log^* n})</math>.<ref>D. Harvey and J. van der Hoeven (2018). "Faster integer multiplication using short lattice vectors", February 2018. {{Arxiv|1802.07932}}</ref> 

En marzo de 2019, Harvey y van der Hoeven publicaron un muy buscado algoritmo <math>O(n\log n)</math>  de multiplicación de enteros que se supone que es asintóticamente óptimo.<ref>{{Cita libro|url=https://hal.archives-ouvertes.fr/hal-02070778|título=Integer multiplication in time O(n log n)|apellidos=Harvey|nombre=David|apellidos2=Van Der Hoeven|nombre2=Joris|fecha=12 de abril de 2019|editorial=|año=|isbn=|ubicación=|páginas=}}</ref><ref>{{Cita noticia|url=https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/|título=Mathematicians Discover the Perfect Way to Multiply|apellidos=Hartnett|nombre=Kevin|fecha=14 de abril de 2019|fechaacceso=15 de abril de 2019|issn=1059-1028}}</ref> 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".<ref>{{Cita noticia|apellidos=Gilbert|nombre=Lachlan|título=Maths whiz solves 48-year-old multiplication problem|url=https://newsroom.unsw.edu.au/news/science-tech/maths-whiz-solves-48-year-old-multiplication-problem|fechaacceso=18 de abril de 2019|editorial=UNSW|fecha=4 de abril de 2019}}</ref>

== Referencias ==
{{Listaref}}
{{Control de autoridades}}
[[Categoría:Algoritmos de precisión arbitraria]]