¿Cuál es el algoritmo más rápido para la multiplicación de dos números de n dígitos?

21

Quiero saber qué algoritmo es más rápido para la multiplicación de dos números de n dígitos. ¡La complejidad del espacio se puede relajar aquí!

Andy
fuente
1
¿Está interesado en la pregunta teórica o en la pregunta práctica?
Yuval Filmus
¡Ambas, pero más inclinadas hacia la práctica!
Andy
1
Para la pregunta práctica, recomiendo usar GMP. Si tienes curiosidad por saber qué usan, mira la documentación o el código fuente.
Yuval Filmus
Nadie lo sabe. Aún no lo hemos encontrado.
JeffE

Respuestas:

22

A partir de ahora, el algoritmo de Fürer de Martin Fürer tiene una complejidad temporal de que utiliza transformadas de Fourier sobre números complejos. Su algoritmo se basa en realidad en el algoritmo de Schönhage y Strassen que tiene una complejidad temporal de Θ ( n log ( n ) log ( log ( n ) ) )nlog(n)2Θ(log(n))Θ(nlog(n)log(log(n)))

Otros algoritmos que son más rápidos que el algoritmo de multiplicación de la escuela primaria son la multiplicación Karatsuba que tiene una complejidad temporal de ≈ y el algoritmo Toom 3 que tiene una complejidad temporal deO ( n 1.585 ) Θ ( n 1.465 )O(nlog23)O(n1.585)Θ(n1.465)

Tenga en cuenta que estos son los algoritmos rápidos. Encontrar el algoritmo más rápido para la multiplicación es un problema abierto en informática.

Referencias

  1. Algoritmo de Fürer
  2. Multiplicación basada en FFT de números grandes
  3. Transformada rápida de Fourier
  4. Multiplicación Toom-Cook
  5. Algoritmo de Schönhage-Strassen
  6. Algoritmo Karatsuba
avi
fuente
Tenga en cuenta el reciente artículo de D. Harvey y J. van der Hoeven (marzo de 2019) que describe un algoritmo con complejidad . O(nlnn)
hardmath
9

Tenga en cuenta que los algoritmos FFT enumerados por avi agregan una constante grande, lo que los hace poco prácticos para números menores a miles + bits.

Además de esa lista, hay algunos otros algoritmos interesantes y preguntas abiertas:

  • Multiplicación de tiempo lineal en un modelo RAM (con precomputación)
  • La multiplicación por una constante es sublineal ( PDF ): esto significa un número sublineal de adiciones que obtiene un total decomplejidad de bits. Esto es esencialmente equivalente a la multiplicación larga (donde se desplaza / suma en función del número des en el número inferior), que es, pero con unaceleración.O(n2logn)1O(n2)O(logn)
  • Sistema de numeración de residuos y otras representaciones de números; La multiplicación es tiempo casi lineal. La desventaja es que la multiplicación es modular y {la detección de desbordamiento, la paridad, la comparación de magnitud} son tan difíciles o casi tan difíciles como convertir el número a una representación binaria o similar y hacer la comparación tradicional; esta conversión es al menos tan mala como la multiplicación tradicional (por el momento, AFAIK).
    • Otras representaciones:
      • [ Representación logarítmica ]: la multiplicación es la suma de la representación logarítmica. Ejemplo:
        16×32=2log216+log232=24+5=29
        • La desventaja es que la conversión hacia y desde la representación logarítmica puede ser tan difícil como la multiplicación o más difícil, la representación también puede ser fraccional / irracional / aproximada, etc. Es probable que otras operaciones (¿suma?) Sean más difíciles.
      • Representación canónica : representa los números como exponentes de la factorización prima. La multiplicación es la suma de los exponentes. Ejemplo:
        36×48=3251×223141=22324151
      • La desventaja es, requiere factores, o factorización, un problema mucho más difícil que la multiplicación. Otras operaciones como la suma son probablemente muy difíciles.
Ensalada Realz
fuente
1
Creo que un enfoque basado en el teorema del residuo / resto chino con los módulos correctos puede conducir a acelerar la multiplicación tradicional incluso con la conversión de regreso; en algún momento esto fue en el capítulo 4 de TAOCP, al menos como una nota al pie. (Todavía no se acerca a los métodos basados ​​en FFT, pero es una nota histórica interesante)
Steven Stadnicki
@StevenStadnicki oh genial, tengo que mirar eso entonces; ¿conoces la complejidad?
Realz Slaw