El algoritmo de Karatsuba es un algoritmo de multiplicación rápida . Fue descubierto por Anatoly Karatsuba en 1960 y publicado en 1962. [1] [2] [3] Reduce la multiplicación de dos números de n dígitos a un máximo multiplicaciones de un solo dígito en general (y exactamente cuando n es una potencia de 2). Por tanto, es asintóticamente más rápido que el algoritmo tradicional , que requiereproductos de un solo dígito. Por ejemplo, el algoritmo de Karatsuba requiere 3 10 = 59,049 multiplicaciones de un solo dígito para multiplicar dos números de 1024 dígitos ( n = 1024 = 2 10 ), mientras que el algoritmo tradicional requiere (2 10 ) 2 = 1,048,576 (una aceleración de 17,75 veces) .
El algoritmo de Karatsuba fue el primer algoritmo de multiplicación asintóticamente más rápido que el algoritmo cuadrático de la "escuela primaria". El algoritmo de Toom-Cook (1963) es una generalización más rápida del método de Karatsuba, y el algoritmo de Schönhage-Strassen (1971) es incluso más rápido, para n suficientemente grande .
Historia
El procedimiento estándar para la multiplicación de dos números de n dígitos requiere un número de operaciones elementales proporcionales a, o en notación Big-O . Andrey Kolmogorov conjeturó que el algoritmo tradicional era asintóticamente óptimo , lo que significa que cualquier algoritmo para esa tarea requeriría operaciones elementales.
En 1960, Kolmogorov organizó un seminario sobre problemas matemáticos en cibernética en la Universidad Estatal de Moscú , donde afirmó laconjeturas y otros problemas en la complejidad de la computación . En una semana, Karatsuba, entonces un estudiante de 23 años, encontró un algoritmo (más tarde se llamó "divide y vencerás") que multiplica dos números de n dígitos enpasos elementales, refutando así la conjetura. Kolmogorov estaba muy emocionado con el descubrimiento; lo comunicó en la próxima reunión del seminario, que luego se dio por terminado. Kolmogorov dio algunas conferencias sobre el resultado de Karatsuba en conferencias de todo el mundo (ver, por ejemplo, "Actas del Congreso Internacional de Matemáticos 1962", págs. 351-356, y también "6 conferencias pronunciadas en el Congreso Internacional de Matemáticos en Estocolmo, 1962 ") y publicó el método en 1962, en las Actas de la Academia de Ciencias de la URSS . El artículo había sido escrito por Kolmogorov y contenía dos resultados sobre la multiplicación, el algoritmo de Karatsuba y un resultado separado de Yuri Ofman ; enumeró a "A. Karatsuba y Yu. Ofman" como los autores. Karatsuba solo se enteró del artículo cuando recibió las reimpresiones del editor. [2]
Algoritmo
Paso básico
El paso básico del algoritmo de Karatsuba es una fórmula que permite calcular el producto de dos números grandes. y usando tres multiplicaciones de números más pequeños, cada uno con aproximadamente la mitad de los dígitos que o , además de algunas adiciones y cambios de dígitos. Este paso básico es, de hecho, una generalización de un algoritmo de multiplicación compleja similar , donde la unidad imaginaria i se reemplaza por una potencia de la base .
Dejar y ser representado como -cadenas de dígitos en alguna base . Para cualquier entero positivo menos que , uno puede escribir los dos números dados como
dónde y son menos que . El producto es entonces
dónde
Estas fórmulas requieren cuatro multiplicaciones y las conocía Charles Babbage . [4] Karatsuba observó quese puede calcular en solo tres multiplicaciones, a costa de algunas adiciones adicionales. Con y como antes se puede observar que
Un problema que ocurre, sin embargo, al computar es que el cálculo anterior de y puede resultar en un desbordamiento (producirá un resultado en el rango ), que requieren un multiplicador con un bit extra. Esto se puede evitar notando que
Este cálculo de y producirá un resultado en el rango de . Este método puede producir números negativos, que requieren un bit adicional para codificar el signo, y aún requerirían un bit adicional para el multiplicador. Sin embargo, una forma de evitar esto es registrar el signo y luego usar el valor absoluto de y para realizar una multiplicación sin signo, después de lo cual el resultado puede ser negado cuando ambos signos diferían originalmente. Otra ventaja es que aunque puede ser negativo, el cálculo final de solo implica adiciones.
Ejemplo
Para calcular el producto de 12345 y 6789, donde B = 10, elija m = 3. Usamos m desplazamientos a la derecha para descomponer los operandos de entrada usando la base resultante ( B m = 1000 ), como:
- 12345 = 12 · 1000 + 345
- 6789 = 6 · 1000 + 789
Solo se utilizan tres multiplicaciones, que operan con números enteros más pequeños, para calcular tres resultados parciales:
- z 2 = 12 × 6 = 72
- z 0 = 345 × 789 = 272205
- z 1 = ( 12 + 345 ) × ( 6 + 789 ) - z 2 - z 0 = 357 × 795 - 72 - 272205 = 283815 - 72 - 272205 = 11538
Obtenemos el resultado simplemente agregando estos tres resultados parciales, desplazados en consecuencia (y luego teniendo en cuenta los acarreos al descomponer estas tres entradas en base 1000 como para los operandos de entrada):
- resultado = z 2 · ( B m ) 2 + z 1 · ( B m ) 1 + z 0 · ( B m ) 0 , es decir
- resultado = 72 · 1000 2 + 11538 · 1000 + 272205 = 83810205 .
Tenga en cuenta que la tercera multiplicación intermedia opera en un dominio de entrada que es menos de dos veces más grande que para las dos primeras multiplicaciones, su dominio de salida es menos de cuatro veces más grande, y los acarreos base- 1000 calculados a partir de las dos primeras multiplicaciones deben tomarse en cuenta al calcular estas dos restas.
Aplicación recursiva
Si n es cuatro o más, las tres multiplicaciones en el paso básico de Karatsuba involucran operandos con menos de n dígitos. Por lo tanto, esos productos se pueden calcular mediante llamadas recursivas del algoritmo de Karatsuba. La recursividad se puede aplicar hasta que los números sean tan pequeños que puedan (o deben) calcularse directamente.
En una computadora con un multiplicador completo de 32 bits por 32 bits , por ejemplo, se podría elegir B = 2 31 =2 147 483 648 y almacene cada dígito como una palabra binaria de 32 bits separada. Entonces, las sumas x 1 + x 0 y y 1 + y 0 no necesitarán una palabra binaria adicional para almacenar el dígito de transferencia (como en el sumador de transferencia de almacenamiento ), y la recursividad de Karatsuba se puede aplicar hasta que los números a multiplicar sean sólo un dígito de largo.
Fórmulas asimétricas similares a Karatsuba
La fórmula original de Karatsuba y otras generalizaciones son simétricas en sí mismas. Por ejemplo, la siguiente fórmula calcula
con 6 multiplicaciones en , dónde es el campo de Galois con dos elementos 0 y 1.
dónde y . Observamos que la suma y la resta son iguales en los campos de la característica 2.
Esta fórmula es simétrica, es decir, no cambia si intercambiamos y en y .
Con base en los segundos algoritmos de división generalizada , [5] Fan et al. encontró la siguiente fórmula asimétrica:
dónde y .
Es asimétrico porque podemos obtener la siguiente nueva fórmula intercambiando y en y .
dónde y .
Análisis de complejidad del tiempo
El paso básico de Karatsuba funciona para cualquier base B y cualquier m , pero el algoritmo recursivo es más eficiente cuando m es igual an / 2, redondeado hacia arriba. En particular, si n es 2 k , para algún número entero k , y la recursividad se detiene solo cuando n es 1, entonces el número de multiplicaciones de un solo dígito es 3 k , que es n c donde c = log 2 3.
Dado que uno puede extender cualquier entrada con cero dígitos hasta que su longitud sea una potencia de dos, se deduce que el número de multiplicaciones elementales, para cualquier n , es como máximo.
Dado que las sumas, restas y cambios de dígitos (multiplicaciones por potencias de B ) en el paso básico de Karatsuba toman un tiempo proporcional an , su costo se vuelve insignificante a medida que n aumenta. Más precisamente, si t ( n ) denota el número total de operaciones elementales que realiza el algoritmo al multiplicar dos números de n dígitos, entonces
para algunas constantes c y d . Por esta relación de recurrencia , el teorema maestro para las recurrencias de divide y vencerás da la asintótica con destino.
De ello se deduce que, para n suficientemente grande , el algoritmo de Karatsuba realizará menos cambios y adiciones de un solo dígito que la multiplicación a mano, aunque su paso básico utiliza más adiciones y cambios que la fórmula sencilla. Sin embargo, para valores pequeños de n , las operaciones adicionales de desplazamiento y adición pueden hacer que se ejecute más lento que el método manual. El punto de retorno positivo depende de la plataforma y el contexto de la computadora . Como regla general, el método de Karatsuba suele ser más rápido cuando los multiplicandos tienen más de 320–640 bits. [6]
Pseudocódigo
Aquí está el pseudocódigo para este algoritmo, usando números representados en base diez. Para la representación binaria de números enteros, basta con reemplazar 10 por 2. [7]
El segundo argumento de la función split_at especifica el número de dígitos a extraer de la derecha : por ejemplo, split_at ("12345", 3) extraerá los 3 dígitos finales, dando: alto = "12", bajo = "345".
procedimiento karatsuba ( num1 , num2 ) if ( num1 < 10 ) o ( num2 < 10 ) return num1 × num2 / * Calcula el tamaño de los números. * / m = min ( size_base10 ( num1 ), size_base10 ( num2 )) m2 = floor ( m / 2 ) / * m2 = ceil (m / 2) también funcionará * / / * Divide las secuencias de dígitos en el medio. * / high1 , low1 = split_at ( num1 , m2 ) high2 , low2 = split_at ( num2 , m2 ) / * 3 llamadas realizadas a números de aproximadamente la mitad del tamaño. * / z0 = karatsuba ( bajo1 , bajo2 ) z1 = karatsuba (( bajo1 + alto1 ), ( bajo2 + alto2 )) z2 = karatsuba ( alto1 , alto2 ) volver ( z2 × 10 ^ ( m2 × 2 )) + (( z1 - z2 - z0 ) × 10 ^ m2 ) + z0
Referencias
- ^ A. Karatsuba y Yu. Ofman (1962). "Multiplicación de muchos números digitales por computadoras automáticas". Actas de la Academia de Ciencias de la URSS . 145 : 293-294. Traducción en la revista académica Physics-Doklady , 7 (1963), págs. 595–596 CS1 maint: posdata ( enlace )
- ^ a b AA Karatsuba (1995). "La complejidad de los cálculos" (PDF) . Actas del Instituto de Matemáticas Steklov . 211 : 169-183. Traducción de Trudy Mat. Inst. Steklova, 211, 186–202 (1995)CS1 maint: posdata ( enlace )
- ^ Knuth DE (1969) El arte de la programación informática . v.2. Addison-Wesley Publ.Co., 724 págs.
- ^ Charles Babbage, Capítulo VIII - De la máquina analítica, números más grandes tratados, pasajes de la vida de un filósofo , Longman Green, Londres, 1864; página 125.
- ^ Haining Fan, Ming Gu, Jiaguang Sun, Kwok-Yan Lam, "Obtener más fórmulas similares a Karatsuba sobre el campo binario", IET Information security Vol. 6 No. 1 págs. 14-19, 2012.
- ^ "Multiplicación de Karatsuba" . www.cburch.com .
- ^ Weiss, Mark A. (2005). Estructuras de datos y análisis de algoritmos en C ++ . Addison-Wesley. pag. 480. ISBN 0321375319.
enlaces externos
- Algoritmo de Karatsuba para la multiplicación de polinomios
- Weisstein, Eric W. "Multiplicación de Karatsuba" . MathWorld .
- Bernstein, DJ, " Multiplicación de varios dígitos para matemáticos ". Cubre Karatsuba y muchos otros algoritmos de multiplicación.