Algoritmo de Karatsuba

Fotografía de Anatolii Alezeevitch Karatsuba al graduarse de la escuela secundaria.

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.​​ El algoritmo consigue reducir la múltiplicación de dos números de n dígitos a como máximo $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.

Historia

El procedimiento estándar para multiplicar dos números de n dígitos requiere un número de operaciones elementales proporcional a n², o $\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 $\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 $\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 $\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.​

El método fue publicado en 1962, en la revista científica soviética Proceedings of the USSR Academy of Sciences.​ 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.​

Algoritmo

El paso básico

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:

x = x₁B^m + x₀

y = y₁B^m + y₀

donde x₀ e y₀ son menores que B^m. El producto es, entonces:

xy = (x₁B^m + x₀)(y₁B^m + y₀)

= z₂ B^2m + z₁ B^m + z₀

donde

z₂ = x₁y₁

z₁ = x₁y₀ + x₀y₁

z₀ = x₀y₀

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

Supongamos z₂ = x₁y₁

Supongamos z₀ = x₀y₀

Supongamos z₁ = (x₁ + x₀)(y₁ + y₀) − z₂ − z₀

ya que

z₁ = (x₁y₁ + x₁y₀ + x₀y₁ + x₀y₀) - x₁y₁ - x₀y₀ = x₁y₀ + x₀y₁

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

z₂ = 0

z₀ = x₀y₀

z₁ = x₁y₀

Ejemplo

Digamos que queremos calcular el producto de 1234 con 5678. Elegimos la base 10 (B = 10) y m = 2. Entonces tenemos:

12 34 = 12 × 10² + 34

56 78 = 56 × 10² + 78

z₂ = 12 × 56 = 672

z₀ = 34 × 78 = 2652

z₁ = (12 + 34)(56 + 78) − z₂ − z₀ = 46 × 134 − 672 − 2652 = 2840

resultado = z₂ × 10^2×2 + z₁ × 10² + z₀ = 672 × 10000 + 2840 × 100 + 2652 = 7006652

Aplicación recursiva

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.

Análisis de eficiencia

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 $3^{\lceil \log _{2}n\rceil }\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:

t(n) = 3 t($\lceil$n/2$\rceil$) + cn + d

para algunas constantes c y d. Para esta relación de recurrencia, el Teorema Maestro da la cota superior asintótica t(n) = $\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]

Referencias

• Karacuba A. A. Berechnungen und die Kompliziertheit von Beziehungen (alemán). Elektron. Informationsverarb. Kybernetik, 11, 603–606 (1975).
• Knuth D.E. The art of computer programming. v.2. Addison-Wesley Publ.Co., 724 pp., Reading (1969).
• Weisstein, Eric W. «Multiplicación de Karatsuba». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Bernstein, D. J., "Multidigit multiplication for mathematicians". Covers Karatsuba and many other multiplication algorithms.
• Multiplicación de Karatsuba en Fast Algorithms y la FEE
• Multiplicación de Karatsuba usando cuadrados de una diferencia

Enlaces externos

• Calculadora en línea que usa el algoritmo de multiplicación de Karatsuba (GPL)

• Datos: Q629940