algoritmo de karatsuba

Algoritmo para la multiplicación de números enteros.

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

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]} 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 /2 dígitos. números y, repitiendo esta reducción, hasta multiplicaciones de un solo dígito como máximo. Por 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 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 una serie de operaciones elementales proporcionales a o en notación O grande . 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 de la complejidad de la computación . Al cabo de 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 dado por finalizado. Kolmogorov dio algunas conferencias sobre el resultado de Karatsuba en conferencias 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 ; enumeraba a "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 divide y vencerás , usando 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 dígitos que o , más algunas sumas y dígitos. turnos. 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}$

Sea y representado 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, a costa de algunas sumas 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, 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

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

z ₂ = 12 × 6 = 72

z ₀ = 345 × 789 = 272205

z ₁ = ( 12 + 345 ) × ( 6 + 789 ) − z ₂ − z ₀ = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

Obtenemos el resultado simplemente sumando estos tres resultados parciales, desplazados en consecuencia (y luego teniendo en cuenta los acarreos descomponiendo 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 .

Tenga en cuenta que la tercera multiplicación intermedia opera en un dominio de entrada que es menos de dos veces mayor que el de las dos primeras multiplicaciones, su dominio de salida es menos de cuatro veces mayor y los acarreos de base 1000 calculados a partir de las dos primeras multiplicaciones deben tenerse en cuenta. cuenta al calcular estas dos restas.

Aplicación recursiva

Si n es cuatro o más, las tres multiplicaciones del paso básico de Karatsuba implican operandos con menos de n dígitos. Por lo tanto, esos productos pueden calcularse mediante llamadas recursivas del algoritmo de Karatsuba. La recursividad se puede aplicar hasta que los números sean tan pequeños que puedan (o deban) calcularse 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 arrastrado (como en el sumador de guardado ), y la recursividad de Karatsuba se puede aplicar hasta que los números a multiplicar sean sólo un dígito de largo.

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

Dado que se pueden 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 . ${\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 cy d . Para esta relación de recurrencia , el teorema maestro para las recurrencias de divide y vencerás da el límite asintótico . ${\displaystyle T(n)=\Theta (n^{\log _{2}3})\,\!}$

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

Implementación

Aquí está el pseudocódigo de este algoritmo, que utiliza números representados en base diez. Para la representación binaria de números enteros, basta con sustituir en todas partes 10 por 2. ^[5]

El segundo argumento de la función split_at especifica el número de dígitos que se extraerán de la derecha : por ejemplo, split_at("12345", 3) extraerá los 3 dígitos finales, dando: alto="12", bajo="345".

función karatsuba ( num1 , num2 ) if ( num1 < 10 o num2 < 10 ) return num1 × num2 /* vuelve a la multiplicación tradicional */ /* Calcula el tamaño de los números. */ m = max ( size_base10 ( num1 ), size_base10 ( num2 )) m2 = piso ( m / 2 ) /* m2 = techo (m / 2) también funcionará */ /* Divida las secuencias de dígitos por la mitad. */ 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 ) retorno ( 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 resultar en 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 la firma 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 realizar una multiplicación sin signo, después de lo cual el resultado puede negarse cuando ambos signos diferían originalmente. Otra ventaja es que, aunque puede ser negativo, el cálculo final de sólo 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 multidigitales 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), págs. 595–596. {{cite journal}}: Mantenimiento CS1: posdata ( 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 CS1: posdata ( 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, números más grandes tratados, 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. pag. 480.ISBN​ 0321375319.

enlaces externos

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