Karatsuba

El algoritmo de Karatsuba es un método rápido para multiplicar números grandes. Normalmente, multiplicar dos números de $n$ dígitos usando el método tradicional cuesta $O(n^2)$ operaciones. Karatsuba reduce esto a aproximadamente $O(n^{\log_2 3}) \approx O(n^{1.585})$, usando una técnica de divide y vencerás.

La idea clave es dividir los números en partes y multiplicarlas inteligentemente para reducir la cantidad de multiplicaciones necesarias.

Cómo funciona

Supongamos que queremos multiplicar dos números $x$ y $y$, ambos con $n$ dígitos.

1. Dividimos cada número en dos partes:

   $$x = a \cdot 10^{m} + b$$ $$y = c \cdot 10^{m} + d$$

   donde:

   • $a$ y $c$ son las partes altas (los dígitos más significativos).
   • $b$ y $d$ son las partes bajas (los dígitos menos significativos).
   • $m$ es aproximadamente la mitad del número de dígitos.

2. Multiplicamos tres combinaciones:

$$ac, \quad bd, \quad (a+b)(c+d)$$

3. Calculamos la parte cruzada usando:

$$ad + bc = (a+b)(c+d) - ac - bd$$

4. Combinamos los resultados:

$$x \cdot y = ac \cdot 10^{2m} + (ad + bc) \cdot 10^{m} + bd$$

Sólo usamos 3 multiplicaciones grandes en vez de 4.

Ejemplo sencillo

Multipliquemos $x = 12$ y $y = 34$ usando Karatsuba:

1. Dividimos los números en partes:

$$x = 12 \Rightarrow a = 1, b = 2$$ $$y = 34 \Rightarrow c = 3, d = 4$$

2. Multiplicamos las combinaciones:

$$ac = 1 \cdot 3 = 3$$ $$bd = 2 \cdot 4 = 8$$ $$(a+b)(c+d) = (1+2)(3+4) = 3 \cdot 7 = 21$$

3. Calculamos la parte cruzada:

$$ad + bc = 21 - 3 - 8 = 10$$

4. Combinamos:

$$x \cdot y = ac \cdot 100 + (ad+bc) \cdot 10 + bd$$ $$x \cdot y = 3 \cdot 100 + 10 \cdot 10 + 8 = 300 + 100 + 8 = 408$$

Y efectivamente, $12 \cdot 34 = 408$.

Ejemplo más complejo

Perfecto, vamos a hacer un ejemplo de Karatsuba con los números:

$$x = 146123, \quad y = 352120$$

Para simplificar, vamos a dividir los números en mitades iguales de 3 dígitos (ya que tienen 6 dígitos cada uno):

$$x = 146123 \Rightarrow a = 146, \, b = 123$$ $$y = 352120 \Rightarrow c = 352, \, d = 120$$

Paso 1: Multiplicaciones principales

1. $ac = 146 \cdot 352$ Para hacerlo más simple, lo calculamos:

$$146 \cdot 352 = 51392$$

2. $bd = 123 \cdot 120 = 14760$

3. $(a+b)(c+d) = (146+123)(352+120) = 269 \cdot 472 = 126968$

Paso 2: Calculamos la parte cruzada

$$ad + bc = (a+b)(c+d) - ac - bd$$ $$ad + bc = 126968 - 51392 - 14760 = 60816$$

Paso 3: Combinamos los resultados

$$x \cdot y = ac \cdot 10^{6} + (ad+bc) \cdot 10^{3} + bd$$

• $ac \cdot 10^6 = 51392 \,000000 = 51\,392\,000\,000$
• $(ad+bc) \cdot 10^3 = 60816\,000 = 60\,816\,000$
• $bd = 14760$

$$x \cdot y = 51\,392\,000\,000 + 60\,816\,000 + 14\,760 = 51\,452\,830\,760$$

Por lo tanto:

$$146123 \cdot 352120 = 51\,452\,830\,760$$