Algoritmo de Harvey-van der Hoeven

El algoritmo de Harvey-van der Hoeven es un algoritmo para multiplicar números enteros de dos bits con complejidad temporal en el modelo de máquina de Turing multicinta . Propuesto por los matemáticos David Harvey de la Universidad de Nueva Gales del Sur y Joris van der Hoeven del Centro Nacional de Investigación Científica de Francia . A partir de 2020, es el algoritmo conocido más rápido para multiplicar números en este modelo, mientras que la estimación de la complejidad temporal de los algoritmos de multiplicación parece inmejorable. $norte$ $O(n\log n)$ $O(n\log n)$

Historia

La cuestión de la existencia de algoritmos rápidos para multiplicar números enteros ocupa un lugar importante en la teoría de la complejidad computacional . Los métodos de multiplicación más conocidos, como la multiplicación apilada, requieren operaciones aritméticas. Esta estimación fue mejorada por primera vez en 1960 por Anatoly Karatsuba , quien propuso un algoritmo para la multiplicación con tiempo de ejecución [1] . En 1971, Schönhage y Strassen propusieron un algoritmo basado en la transformada rápida de Fourier en el tiempo [2] . En el mismo trabajo, propusieron la hipótesis de que el algoritmo de multiplicación óptimo requiere operaciones elementales. Sin embargo, durante mucho tiempo la cota superior dada por el algoritmo de Schönhage y Strassen permaneció sin mejoras. Recién en 2007, 36 años después, Martin Fuhrer propuso un algoritmo con tiempo de ejecución para una constante no especificada , donde es un logaritmo iterado [3] . Posteriormente, Harvey y van der Hoeven mejoraron esta estimación primero a [4] y luego a , confirmando así el límite superior propuesto en la conjetura de Schönhage y Strassen [5] . El algoritmo es de gran importancia teórica, ya que logra un límite inferior hipotético para el tiempo de ejecución de los algoritmos de multiplicación de números en el modelo de máquina de Turing multicinta. Sin embargo, la aceleración práctica se logra solo en números cuya longitud binaria excede un poco, mientras que el número de partículas en el universo observable se estima como [6] . $O(n^{2})$ ${\ estilo de visualización O (n ^ {\ log _ {2} 3})}$ $O(n\log n\log \log n)$ $O(n\log n)$ $O(n\log n\cdot K^{\log ^{*}n})$ ${\ estilo de visualización K> 1}$ $\log ^{*}n$ $O(n\log n\cdot 4^{\log ^{*}n})$ $O(n\log n)$ $2^{1729^{12}}\aproximadamente 2^{7\cdot 10^{38}}$ ${\ estilo de visualización 2^{270}}$

Notas

↑ A. Karatsuba, Y. Offman. Multiplicación de números de varios valores en autómatas // Dokl. Academia de Ciencias de la URSS. - 1962. - 9 de febrero ( vol. 145 , núm. 2 ). - S. 293-294 .
↑ A. Schönhage, V. Strassen. Schnelle Multiplikation großer Zahlen (alemán) // Informática. — 1971-09-01. — bd. 7 , H. 3 . — S. 281–292 . — ISSN 1436-5057 . -doi : 10.1007/ BF02242355 .
↑ Martín Furer. Multiplicación de enteros más rápida (inglés) // SIAM Journal on Computing. — 2009-01. — vol. 39 , edición. 3 . — pág. 979–1005 . - ISSN 1095-7111 0097-5397, 1095-7111 . -doi : 10.1137/ 070711761 .
↑ David Harvey, Joris van der Hoeven. Multiplicación de enteros más rápida utilizando vectores reticulares cortos // The Open Book Series. — 2019-01-28. — vol. 2 , edición. 1 . — pág. 293–310 . — ISSN 2329-9061 2329-907X, 2329-9061 . -doi : 10.2140 / obs.2019.2.293 .
↑ David Harvey, Joris Van Der Hoeven. Multiplicación de enteros en el tiempo O(n log n ) . — 2019. Archivado el 8 de abril de 2019 en Wayback Machine .
↑ Érica Klarreich. La multiplicación alcanza el límite de velocidad // Comunicaciones del ACM. - 2019. - 20 de diciembre. -doi : 10.1145/ 3371387 . Archivado desde el original el 30 de junio de 2020.

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin