Problema de multiplicação de inteiros

Entrada:

 - dois inteiros x e y com n dígitos cada.
 
Saída:

 - o produto x vezes y.
 
Vamos avaliar a eficiência do algoritmo contando o número de operações básicas que ele realiza. No contexto deste problema uma operação básica é uma soma ou multiplicação envolvendo números com apenas um dígito cada.


Exemplo:

 - multiplicar 5678 x 1234 = 7006652.
 - analisar o número de operações básicas realizadas em função de n.
 - concluir que o número de operações básicas cresce de modo proporcional a uma função quadrática em n, digamos 4 n^2.



"Perhaps the most important principle for the good algorithm designer is to refuse to be content" - Aho, Hopcroft and Ullman, The Design and Analysis of Computer Algorithms, 1974.

ou, simplesmente, conseguimos fazer melhor?



Exemplo do algoritmo de Karatsuba:

 - Quebrar 5678 em xl = 56 e xr = 78
 - Quebrar 1234 em yl = 12 e yr = 34
 - Multiplicar xl * yl = 672 (a)
 - Multiplicar xr * yr = 2652 (b)
 - Multiplicar (xl + xr) * (yl + yr) = (56 + 78) * (12 + 34) = 134 * 46 = 6164 (c)
 - Calcular c - a - b = 6164 - 672 - 2652 = 2840 (d)
 - Combinar a*10^4 + d*10^2 + b = 6720000 + 284000 + 2652 = 7006652


Algoritmo recursivo simples:

 - Dividir os números x e y em xl, xr e yl, yr, respectivamente, de modo que os dígitos mais significativos fiquem nas metades do tipo l e os menos significativos fiquem nas metades do tipo r.
 - Dada a expressão x * y = (xl * 10^n/2 + xr) * (yl * 10^n/2 + yr)
                          = 10^n * (xl * yl) + 10^n/2 * (xl * yr + xr * yl) + xr * yr (***)
 - Já que xl, xr, yl, yr tem metade dos dígitos dos números originais, calcule recursivamente os produtos presentes na expressão anterior.
 - Quantos produtos são?
 - Qual o caso base da recursão?
 - De posse do resultado de cada produto basta multiplicá-lo pela potencia de 10 adequada e obter o resultado seguindo a expressão anterior.
 - O tempo gasto por esse algoritmo em função do número n de dígitos dos números da entrada é dado pela recorrência:
    - T(n) = 4 * T(n/2) + O(n)


Algoritmo de Karatsuba:

 - x * y = 10^n * (xl * yl) + 10^n/2 * (xl * yr + xr * yl) + xr * yr (***)
 - não nos interessam os valores xl * yr e xr * yl individualmente, mas só a soma deles
 - será que conseguimos obter este resultado sem usar duas chamadas recursivas (uma para cada produto)?
 - calculemos recursivamente xl * yl [aux1] e xr * yr [aux2]
 - usando um truque que Carl Friedrich Gauss desenvolveu para multiplicar números complexos temos:
   - (xl + xr) * (yl + yr) = xl * yl + xl * yr + xr * yl + xr * yr
 - portanto, se calcularmos recursivamente (xl + xr) * (yl + yr) [aux3]
 - podemos fazer [aux3] - [aux1] - [aux2] = (xl * yr + xr * yl)
 - que é o valor que queríamos obter.
 - Note que desta forma só precisamos de 3 chamadas recursivas.
 - O tempo gasto por esse algoritmo em função do número n de dígitos dos números da entrada é dado pela recorrência:
    - T(n) = 3 * T(n/2) + O(n)