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 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.

Contexto

El algoritmo Schönhage – Strassen utiliza la transformación rápida de Fourier (FFT) para calcular productos enteros en tiempo $O(n\log n\cdot \log \log n)$ y sus autores, Arnold Schönhage y Volker Strassen, conjeturan un límite inferior de Plantilla:Nowrap El algoritmo de Fürer reduce la brecha entre estos dos límites. Se puede usar para multiplicar enteros de longitud $n$ a tiempo $O(n\log n\cdot 2^{O({\log }^{*}n)})$ donde log* n es el logaritmo iterado. La diferencia entre los términos $\log \log n$ y $2^{{\log }^{*}n}$, desde el punto de vista de la complejidad, es la ventaja asintótica en el algoritmo de Fürer para enteros mayores que $2^{2^{64}}$. Sin embargo, la diferencia entre estos términos para valores realistas de $n$ es muy pequeño.

Algoritmos mejorados

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. Se ha estimado que se vuelve más rápido que Schönhage-Strassen para entradas que exceden una longitud de $10^{10^{4796}}$.

En 2015, Harvey, van der Hoeven y Lecerf dieron un nuevo algoritmo que logra un tiempo de ejecución de $O(n\log n\cdot 2^{3{\log }^{*}n})$ haciendo explícita la constante implícita en el exponente de $O({\log }^{*}n)$. También propusieron una variante de su algoritmo que logra $O(n\log n\cdot 2^{2{\log }^{*}n})$ 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. Sin embargo, sigue siendo tan poco práctico como todas las demás implementaciones de este algoritmo.

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 $O(n\log n\cdot 2^{2{\log }^{*}n})$. 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.

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 $O(n\log n\cdot 2^{2{\log }^{*}n})$.

En marzo de 2019, Harvey y van der Hoeven publicaron un muy buscado algoritmo $O(n\log n)$ de multiplicación de enteros que se supone que es asintóticamente óptimo. 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".