Algoritmo Karatsuba

Algoritmo para la multiplicación de números enteros

Multiplicación de Karatsuba de az+b y cz+d (en el recuadro), y 1234 y 567 con z=100. Las flechas de color magenta indican multiplicación, ámbar, suma, plata, resta y cian, desplazamiento a la izquierda. (A), (B) y (C) muestran recursión con z=10 para obtener valores intermedios.

El algoritmo Karatsuba es un algoritmo de multiplicación rápida . Fue descubierto por Anatoly Karatsuba en 1960 y publicado en 1962. ^{[1] [2] [3]} Es un algoritmo de divide y vencerás que reduce la multiplicación de dos números de n dígitos a tres multiplicaciones de números de n /2 dígitos y, repitiendo esta reducción, a como máximo multiplicaciones de un solo dígito. Por lo tanto, es asintóticamente más rápido que el algoritmo tradicional , que realiza productos de un solo dígito. ${\displaystyle n^{\log _{2}3}\approx n^{1.58}}$ ${\displaystyle n^{2}}$

El algoritmo de Karatsuba fue el primer algoritmo de multiplicación asintóticamente más rápido que el algoritmo cuadrático de "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 aún más rápido, para valores n suficientemente grandes .

Historia

El procedimiento estándar para la multiplicación de dos números de n dígitos requiere una cantidad de operaciones elementales proporcional a , o en notación O mayúscula . Andrey Kolmogorov conjeturó que el algoritmo tradicional era asintóticamente óptimo , lo que significa que cualquier algoritmo para esa tarea requeriría operaciones elementales. ${\displaystyle n^{2}\,\!}$ ${\displaystyle O(n^{2})\,\!}$ ${\displaystyle \Omega (n^{2})\,\!}$

En 1960, Kolmogorov organizó un seminario sobre problemas matemáticos en cibernética en la Universidad Estatal de Moscú , donde planteó la conjetura y otros problemas en la complejidad del cálculo . En una semana, Karatsuba, entonces un estudiante de 23 años, encontró un algoritmo que multiplica dos números de n dígitos en pasos elementales, refutando así la conjetura. Kolmogorov estaba muy entusiasmado con el descubrimiento; lo comunicó en la siguiente reunión del seminario, que luego fue clausurado. Kolmogorov dio algunas conferencias sobre el resultado de Karatsuba en congresos por 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 ; en él figuraban "A. Karatsuba y Yu. Ofman" como autores. Karatsuba sólo se enteró del artículo cuando recibió las reimpresiones del editor. ^[2] ${\displaystyle \Omega (n^{2})\,\!}$ ${\displaystyle O(n^{\log _{2}3})}$

Algoritmo

Paso básico

El principio básico del algoritmo de Karatsuba es el de divide y vencerás , que utiliza una fórmula que permite calcular el producto de dos números grandes y utilizar tres multiplicaciones de números más pequeños, cada una con aproximadamente la mitad de dígitos que o , más algunas adiciones y desplazamientos de dígitos. Este paso básico es, de hecho, una generalización de un algoritmo de multiplicación complejo similar , donde la unidad imaginaria i se reemplaza por una potencia de la base . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

Sean y representados como cadenas de dígitos en alguna base . Para cualquier entero positivo menor que , se pueden escribir los dos números dados como ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle B}$ ${\displaystyle m}$ ${\displaystyle n}$

${\displaystyle x=x_{1}B^{m}+x_{0},}$

${\displaystyle y=y_{1}B^{m}+y_{0},}$

donde y son menores que . El producto es entonces ${\displaystyle x_{0}}$ ${\displaystyle y_{0}}$ ${\displaystyle B^{m}}$

${\displaystyle {\begin{aligned}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})\\&=x_{1}y_{1}B^{2m}+(x_{1}y_{0}+x_{0}y_{1})B^{m}+x_{0}y_{0}\\&=z_{2}B^{2m}+z_{1}B^{m}+z_{0},\\\end{aligned}}}$

dónde

${\displaystyle z_{2}=x_{1}y_{1},}$

${\displaystyle z_{1}=x_{1}y_{0}+x_{0}y_{1},}$

${\displaystyle z_{0}=x_{0}y_{0}.}$

Estas fórmulas requieren cuatro multiplicaciones y eran conocidas por Charles Babbage . ^[4] Karatsuba observó que se puede calcular en sólo tres multiplicaciones, al costo de unas pocas adiciones adicionales. Con y como antes y se puede observar que ${\displaystyle xy}$ ${\displaystyle z_{0}}$ ${\displaystyle z_{2}}$ ${\displaystyle z_{3}=(x_{1}+x_{0})(y_{1}+y_{0}),}$

${\displaystyle {\begin{aligned}z_{1}&=x_{1}y_{0}+x_{0}y_{1}\\&=(x_{1}+x_{0})(y_{0}+y_{1})-x_{1}y_{1}-x_{0}y_{0}\\&=z_{3}-z_{2}-z_{0}.\\\end{aligned}}}$

Por lo tanto, sólo se requieren tres multiplicaciones para calcular y ${\displaystyle z_{0},z_{1}}$ ${\displaystyle z_{2}.}$

Ejemplo

Para calcular el producto de 12345 y 6789, donde B = 10, elegimos 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

Sólo se utilizan tres multiplicaciones, que operan sobre números enteros más pequeños, para calcular tres resultados parciales:

z2 = 12 _× 6 = 72

z0 = 345 _× 789 = 272205

z1 = ( 12 + 345 ) × ( 6 + 789 ) − z2 ₋ z0 = 357 × ₇₉₅ − 72 − 272205 = 283815 − 72 − 272205 = ₁₁₅₃₈

Obtenemos el resultado simplemente sumando estos tres resultados parciales, desplazados en consecuencia (y luego tomando en cuenta los acarreos al descomponer estas tres entradas en base 1000 como para los operandos de entrada):

resultado = z ₂ · ( B ^m ) ² + z ₁ · ( B ^m ) ¹ + z ₀ · ( B ^m ) ⁰ , es decir

resultado = 72 · 1000 ² + 11538 · 1000 + 272205 = 83810205 .

Téngase 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 de base 1000 calculados a partir de las dos primeras multiplicaciones deben tenerse 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 recursión se puede aplicar hasta que los números sean tan pequeños que se puedan (o deban) calcular directamente.

En una computadora con un multiplicador completo de 32 bits por 32 bits , por ejemplo, se podría elegir B ​​= 2 ³¹ y almacenar cada dígito como una palabra binaria separada de 32 bits. Entonces, las sumas x ₁ + x ₀ e y ₁ + y ₀ no necesitarán una palabra binaria adicional para almacenar el dígito de arrastre (como en el sumador de arrastre-guardado ), y se puede aplicar la recursión Karatsuba hasta que los números a multiplicar tengan solo un dígito de longitud.

Complejidad temporalanálisis

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 a n /2, redondeado hacia arriba. En particular, si n es 2 ^k , para algún entero k , y la recursión 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 ₂ 3.

Como se puede ampliar 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 . ${\displaystyle 3^{\lceil \log _{2}n\rceil }\leq 3n^{\log _{2}3}\,\!}$

Dado que las sumas, restas y desplazamientos de dígitos (multiplicaciones por potencias de B ) en el paso básico de Karatsuba toman un tiempo proporcional a n , 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

${\displaystyle T(n)=3T(\lceil n/2\rceil )+cn+d}$

para algunas constantes c y d . Para esta relación de recurrencia , el teorema maestro para recurrencias de divide y vencerás proporciona el límite asintótico . ${\displaystyle T(n)=\Theta (n^{\log _{2}3})\,\!}$

De ello se deduce que, para valores de n suficientemente grandes , el algoritmo de Karatsuba realizará menos desplazamientos y sumas de un solo dígito que la multiplicación manual, aunque su paso básico utiliza más sumas y desplazamientos que la fórmula simple. Sin embargo, para valores pequeños de n , las operaciones de desplazamiento y suma adicionales pueden hacer que funcione más lento que el método manual.

Implementación

A continuación se presenta el pseudocódigo de este algoritmo, que utiliza números representados en base diez. Para la representación binaria de los números enteros, basta con reemplazar en todas partes 10 por 2. ^[5]

El segundo argumento de la función split_at especifica la cantidad de dígitos a extraer de la derecha : por ejemplo, split_at("12345", 3) extraerá los 3 dígitos finales, dando: high="12", low="345".

function karatsuba ( num1 , num2 ) if ( num1 < 10ornum2 < 10 ) returnnum1 × num2 / * volver a la multiplicación tradicional */ / * Calcula el tamaño de los números. */ m = max ( 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 recursivas 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 ) return ( z2 × 10 ^ ( m2 × 2 )) + (( z1 - z2 - z0 ) × 10 ^ m2 ) + z0                                                                               

Un problema que ocurre durante la implementación es que el cálculo anterior de y para puede generar un desbordamiento (producirá un resultado en el rango ), lo que requiere un multiplicador que tenga un bit adicional. Esto se puede evitar teniendo en cuenta que ${\displaystyle (x_{1}+x_{0})}$ ${\displaystyle (y_{1}+y_{0})}$ ${\displaystyle z_{1}}$ ${\displaystyle B^{m}\leq {\text{result}}<2B^{m}}$

${\displaystyle z_{1}=(x_{0}-x_{1})(y_{1}-y_{0})+z_{2}+z_{0}.}$

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 originalmente diferían. Otra ventaja es que, aunque puede ser negativo, el cálculo final de solo implica sumas. ${\displaystyle (x_{0}-x_{1})}$ ${\displaystyle (y_{1}-y_{0})}$ ${\displaystyle -B^{m}<{\text{result}}<B^{m}}$ ${\displaystyle (x_{0}-x_{1})}$ ${\displaystyle (y_{1}-y_{0})}$ ${\displaystyle (x_{0}-x_{1})(y_{1}-y_{0})}$ ${\displaystyle z_{1}}$

Referencias

1. A. Karatsuba y Yu. Ofman (1962). "Multiplicación de números de varios dígitos mediante 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), pp. 595-596 {{cite journal}}: Mantenimiento de CS1: postscript ( enlace )
2. AA Karatsuba (1995). "La complejidad de los cálculos" (PDF) . Actas del Instituto Steklov de Matemáticas . 211 : 169–183. Traducción de Trudy Mat. Inst. Steklova, 211, 186–202 (1995) {{cite journal}}: Mantenimiento de CS1: postscript ( enlace )
3. Knuth DE (1969) El arte de la programación informática . v.2. Addison-Wesley Publ.Co., 724 págs.
4. Charles Babbage, Capítulo VIII – De la máquina analítica, tratados sobre números mayores, pasajes de la vida de un filósofo, Longman Green, Londres, 1864; página 125.
5. Weiss, Mark A. (2005). Estructuras de datos y análisis de algoritmos en C++ . Addison-Wesley. pág. 480. ISBN. 0321375319.

Enlaces externos

• Algoritmo de Karatsuba para la multiplicación de polinomios
• Weisstein, Eric W. "Multiplicación de Karatsuba". MundoMatemático .
• Bernstein, DJ, "Multiplicación de varios dígitos para matemáticos". Trata sobre Karatsuba y muchos otros algoritmos de multiplicación.