Multiplicar 2 Enteros De N Cifras Con Un Algoritmo Clásico

R: Multiplicar 2 enteros de n cifras con un algoritmo clásico tiene un O(n2), para ello existe un algoritmo que utiliza la metodología de divide y vencerás.

Hay otras formas de multiplicar números como por ejemplo la multiplicación rusa que tiene el mismo rendimiento y la otra forma es la de divide y vencerás la cual consta en realizar cuatro multiplicaciones, pero no existe una mejora de rendimiento. Lo que sí existe es una mejora para el algoritmo de divide y vencerás, la cual consiste en reducir a 3 multiplicaciones de enteros de n/2 cifras, para ello se igualan las cifras de ambos operando y se dividen ambas cifras por la mitad.

Ej: 981 * 1234, entonces quedaría 0981 y 1234, luego se dividen ambas cifras por la mitad quedando w=09, x=81, y=12, z=34.

Luego 981 = 102w + x 1234 = 102y + z

981 * 1234 = (102w + x) * (102y + z) = 104wy + 102(wz + xy) + xz

Ahora se necesita sumar wz y xy en una sola multiplicación ya que

r = (w+x)(y+z) = wy + (wz +xy) + xz

Esto se traduce en tener solo 3 multiplicaciones a saber, las que son:

p = wy = 09 * 12 = 108

q = xz = 81 * 34 = 2754

r = (w+x)(y+z) = 90 * 46 =4140

Quedando finalmente 981 * 1234 = 104 p + 102 (r–p-q) + q =

1080000+127800+2754 = 1210554

...