Karatsuba Multiplicación

Question

Karatsuba la ecuación para reducir la cantidad de tiempo que se tarda en la fuerza bruta de la multiplicación es el siguiente (creo que este es un divide y vencerás algoritmo):

$$ x y = 10^n(ac) + 10^{n/2}(ad + bc) + bd $$

Mi pregunta es esta. Cuando hice el $10^{n/2}$$10^n$?

Gracias

Answer 1

Karatsuba multiplicación trabaja como esto:

Deje $x = a10^n + b$$y = c10^n + d$, e $a,b,c,d < 10^n$. A continuación, para encontrar el producto $xy$, se observa que el $xy = ac10^{2n} + (ad + bc)10^n + bd$. La ventaja del algoritmo es que usted puede calcular los productos de $ac, ad, bc$$bd$, todos los cuales tienen un tamaño mucho menor que el original (para $n$).

Tenga en cuenta que yo uso $2n$ $n$ en lugar de $n$$n/2$, pero la idea es la misma.

Answer 2

n representa el número de dígitos de los factores que se han multiplicado.

Por ejemplo:

1234 x 5678 = 7006652

Así 1234 como 4 dígitos, como para 5678. Entonces se dice que n = 4, ya que cada factor de 4 dígitos.

Ahora aplicar la ecuación y ver por ti mismo:

1234*5678 = 10^4(12*56) + 10^2(12*78 + 34*56) + 34*78 = 7006652