Supongamos que se quieren multiplicar dos enteros de n cifras, con n lo suficientemente grande como para no caber en una variable entera (n>10). El algoritmo que todo el mundo usaría primero sería el mismo que se utiliza para resolver el problema "a mano", esto es, multiplicar cada cifra del segundo número por todas las del primero, y sumar los resultados:

  1111
*  123
------
  3333
 2222
1111
------
136653

El tiempo de ejecución de este algoritmo es de O(n²), pero se puede intentar mejorar. Ahora dividimos los números en dos partes iguales; el 1111 se dividiría en 11·10² + 11 y el 123 se dividiría en 1·10² + 23. Ahora la multiplicación se puede hacer:

X_iX_d·Y_iY_d = X_i·Y_i·10ⁿ + (X_i·Y_d+X_d·Y_i)·10^n/2 + X_d·Y_d
1111·123 = 11·10²·1·10² + 11·10²·23 + 1·10²·11 + 11*23 = 136653

Teniendo en cuenta que la multiplicación por una potencia de 10 consiste en añadir ceros, y que la suma es una operación lineal, ahora el problema queda subdividido en cuatro subproblemas de tamaño n/2, con un tiempo de combinación de soluciones lineal, con lo que T(n) = 4·T(n/2) + O(n), y como se vio arriba esto equivale a T(n) = O(n²), lo que no mejora el algoritmo inicial. Para mejorarlo habría que dividir el problema en menos de 4 subproblemas. Esto se puede hacer teniendo en cuenta que X_i·Y_d+X_d·Y_i = (X_i-X_d)·(Y_d-Y_i) + X_i·Y_i + X_d·Y_d , con lo que sólo se necesitan tres multiplicaciones diferentes, siendo ahora el tiempo de ejecución T(n) = 3·T(n/2) + O(n), o lo que es lo mismo, T(n) = O(n^log₂3) = O(n^1.59), que mejora considerablemente el tiempo cuadrático del método inicial. Para acabar el algoritmo bastaría con añadir una recursión que vaya solucionando los subproblemas, y poner el umbral en, por ejemplo, 4 cifras, con lo que se podría realizar la multiplicación normal.

Código

Código fuente en C