Algoritmo de Karatsuba
Si n = 210 = 1024, en particular, el cómputo final exacto es 310 = 59.049 y (210)2 = 1.048.576, respectivamente.
El algoritmo de Karatsuba es un claro ejemplo del paradigma divide y vencerás, concretamente del algoritmo de partición binaria.
En 1952, Andrey Kolmogorov intentó probar que el algoritmo clásico era óptimo asintóticamente, queriendo demostrar así que cualquier algoritmo para esta tarea requeriría
operaciones elementales, refutando así la suposición inicial de Kolmogorov.
Kolmogorov se sintió muy desilusionado por tal descubrimiento, y lo hizo público en el que sería su siguiente y último encuentro del seminario.
[1] El artículo había sido escrito por Kolmogorov, posiblemente en colaboración con Yuri Ofman, pero nombraba a "A. Karatsuba y Yu.
Supongamos que x e y están representados como cadenas de n dígitos en alguna base B.
Para cualquier entero positivo m menor que n, uno puede dividir los dos números dados de la manera siguiente: donde x0 e y0 son menores que Bm.
Entonces tenemos: Si n es cuatro o mayor que cuatro, las tres multiplicaciones en el paso básico de Karatsuba suponen operandos con menos de n dígitos.
Por lo tanto, estos productos pueden ser calculados por llamadas recursivas del algoritmo de Karatsuba.
En un ordenador con un multiplicador ALU completo de 32 x 32 bits, por ejemplo, uno podría escoger B = 231 = 2,147,483,648 o B = 109 = 1,000,000,000, y almacenar cada dígito como una palabra binaria de 32 bits.
Entonces las sumas x1 + x0 e y1 + y0 no necesitarán un dígito de acarreo extra (como en un sumador sin acarreo (carry-save adder)), y la recurrencia de Karatsuba puede ser aplicada hasta que los números tengan solo un dígito.
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 por exceso.
Ya que las sumas, las restas, y los desplazamientos de dígitos (multiplicaciones por potencias de B) en el paso básico de Karatsuba requieren tiempos proporcionales a n, su coste se hace insignificante a medida que crece n. Precisamente, si t(n) denota el número total de operaciones elementales que el algoritmo realiza cuando se multiplican dos números de n dígitos, entonces podemos escribir: para algunas constantes c y d. Para esta relación de recurrencia, el Teorema Maestro da la cota superior asintótica t(n) =
Se tiene que, para un n suficientemente grande, el algoritmo de Karatsuba realizará menos desplazamientos y sumas de un solo dígito que la multiplicación a mano, incluso cuando su paso básico use más sumas y desplazamientos que la fórmula sencilla.
Para valores pequeños de n, sin embargo, los desplazamientos y operaciones de suma pueden hacerlo ir más lentamente que el método a mano.
Por norma general, Karatsuba normalmente es más rápido cuando los multiplicandos son del orden 2320 ≈ 2×1096 o mayor [1][2]
