Algoritmo de Karatsuba

El algoritmo de Karatsuba es un procedimiento para multiplicar números grandes eficientemente, que fue descubierto por Anatolii Alexeevitch Karatsuba en 1960 y publicado en 1962.^[1]​^[2]​ El algoritmo consigue reducir la múltiplicación de dos números de n dígitos a como máximo ${displaystyle 3n^{log _{2}3}approx 3n^{1.585}}$ multiplicaciones de un dígito. Es, por lo tanto, más rápido que el algoritmo clásico, que requiere n² productos de un dígito. Si n = 2¹⁰ = 1024, en particular, el cómputo final exacto es 3¹⁰ = 59.049 y (2¹⁰)² = 1.048.576, respectivamente.

El algoritmo de Toom-Cook es una generalización más rápida del de Karatsuba. Para un n suficientemente grande, el algoritmo de Schönhage-Strassen es mejor que el algoritmo de Karatsuba.

El algoritmo de Karatsuba es un claro ejemplo del paradigma divide y vencerás, concretamente del algoritmo de partición binaria.

El procedimiento estándar para multiplicar dos números de n dígitos requiere un número de operaciones elementales proporcional a n², o ${displaystyle Theta (n^{2})}$ en la Notación O grande. 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 ${displaystyle Omega (n^{2})}$ operaciones elementales.

En otoño de 1960, Kolmogorov organizó un seminario acerca de problemas matemáticos de cibernética en la Universidad Estatal de Moscú, donde planteó su suposición de ${displaystyle Omega (n^{2})}$ y otros problemas de complejidad computacional. En una semana, Karatsuba, un estudiante de 25 años, encontró un algoritmo divide y vencerás que multiplicaba dos números de n dígitos en ${displaystyle Theta (n^{log _{2}3})}$ 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.^[2]​

El método fue publicado en 1962, en la revista científica soviética Proceedings of the USSR Academy of Sciences.^[1]​ El artículo había sido escrito por Kolmogorov, posiblemente en colaboración con Yuri Ofman, pero nombraba a "A. Karatsuba y Yu. Ofman" como los autores. Karatsuba solo se dio cuenta de la publicación cuando recibió una copia del artículo por parte de la editorial de la revista.^[2]​

El paso básico del algoritmo de Karatsuba es una fórmula que nos permite calcular el producto de dos números grandes x e y usando tres multiplicaciones de números más pequeños, cada uno con más o menos la mitad de los dígitos de x e y, más algunas sumas y desplazamientos de dígitos.

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 x₀ e y₀ son menores que B^m. El producto es, entonces:

donde

Estas fórmulas requieren cuatro multiplicaciones. Karatsuba observó que podemos calcular xy en solo tres multiplicaciones, por el coste de unas sumas adicionales:

ya que

Si y₁ = 0, solo hay que realizar dos multiplicaciones puesto que:

Digamos que queremos calcular el producto de 1234 con 5678. Elegimos la base 10 (B = 10) y m = 2. 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. La recursividad puede ser aplicada hasta que los números sean tan pequeños que pueden (o deben) ser calculados directamente.

En un ordenador con un multiplicador ALU completo de 32 x 32 bits, por ejemplo, uno podría escoger B = 2³¹ = 2,147,483,648 o B = 10⁹ = 1,000,000,000, y almacenar cada dígito como una palabra binaria de 32 bits. Entonces las sumas x₁ + x₀ e y₁ + y₀ 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. En particular, si n es 2^k, para un entero k, y la recursividad se para solo cuando n es 1, entonces el número de multiplicaciones de un solo dígito es 3^k, es decir, n^c donde c = log₂3.

Ya que uno puede ampliar cualquier entrada con dígitos cero hasta que su longitud sea una potencia de dos, se tiene que el número de multiplicaciones elementales, para cualquier n, es a lo sumo ${displaystyle 3^{lceil log _{2}n ceil }leq 3n^{log _{2}3}}$.

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) = ${displaystyle Theta }$(n^{log(3)/log(2)}).

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. Todo depende de la plataforma del ordenador y del contexto. Por norma general, Karatsuba normalmente es más rápido cuando los multiplicandos son del orden 2³²⁰ ≈ 2×10⁹⁶ o mayor [1][2]

---