Quanto tempo é necessário para multiplicar dois números naturais? Se os números têm m e n dígitos respectivamente, o algoritmo usual consome tempo proporcional a m × n.
×1414213562373095048801688724209
×2223141592653589793238462643383
222222222222222222222222222222???
É difícil imaginar um algoritmo mais rápido que o usual se m e n forem pequenos (algumas centenas, digamos). Mas existe um algoritmo que é bem mais rápido quando m e n são grandes (como acontece em criptografia, por exemplo).
O algoritmo de Karatsuba (Карацуба) usa o método de divisão e conquista. A análise do desempenho do algoritmo leva a uma interessante recorrência.
Esta página ensina algumas lições de caráter geral: (1) para muitos problemas, existem algoritmos surpreendentes mais rápidos que o algoritmo usual; (2) às vezes, a superioridade do algoritmo mais sofisticado só se manifesta nas instâncias muito grandes do problema; (3) as técnicas de resolução de recorrências são capazes de fazer uma análise muito precisa do desempenho de algoritmos recursivos.
O problema da multiplicação de números naturais consiste no seguinte: Dados números naturais u e v, calcular o produto u × v.
Usaremos notação decimal para representar números naturais. Nessa notação, um dígito é qualquer número natural no intervalo 0 .. 9. Você deve imaginar que cada número natural é representado por um vetor de dígitos decimais. Esse vetor é a expansão decimal do número. Mas nossa discussão será conduzida num nível de abstração alto, sem manipulação explícita desse vetor.
Ao discutir o problema, é conveniente explicitar o tamanho dos números a multiplicar. Diremos que um número natural u tem no máximo n dígitos se u < 10n. Assim, o problema passa a ter a seguinte forma:
Problema da multiplicação: Dados números naturais u e v com no máximo n dígitos cada, calcular a expansão decimal do produto u × v.
O algoritmo usual de multiplicação resolve o problema em tempo proporcional a n². Existe algoritmo mais rápido?
Exemplo A: Veja o rastreamento da execução do algoritmo usual ao multiplicar 9999 por 7777:
22229999
22227777
22269993
2269993
269993
69993
77762223
Sejam u e v dois números com no máximo n dígitos cada. Suponha, por enquanto, que n é par. Seja p o número formado pelos n/2 primeiros dígitos (dígitos mais significativos) de u e seja q o número formado pelos n/2 últimos dígitos (dígitos menos significativos) de u. Então
u = p × 10n/2 + q .
Defina r e s analogamente para v, de modo que v = r × 10n/2 + s. Teremos então
| u × v = p × r × 10n + (p × s + q × r) × 10n/2 + q × s . | (A) |
O lado direito da equação tem apenas 4 multiplicações verdadeiras (a saber, p por r, p por s, q por r e q por s). A multiplicação por 10n não conta como multiplicação porque representa um mero deslocamento (= shift) do vetor todo para a esquerda. Esse deslocamento é muito mais barato que uma multiplicação pois consome meras n unidades de tempo. Observação análoga vale para a multiplicação por 10n/2.
A expressão (A) reduz a multiplicação de dois números com no máximo n dígitos cada a quatro multiplicações de números com no máximo n/2 dígitos cada. Essa é a fase de divisão do método de divisão e conquista; as fases de conquista e combinação serão discutidas nas seções seguintes.
| p × r | p × s |
| q × r | q × s |
Infelizmente, essa redução de 1 multiplicação grande para 4 pequenas não basta, por si só, para tornar a multiplicação mais eficiente que a usual, como mostra um dos exercícios abaixo.
Exemplo B: Quero multiplicar 6514202 por 9898989. O resultado das contas pode ser resumido assim:
22222226514202__u = p × 104 + q
22222229898989__v = r × 104 + s
64383929898989__p × r
22258518392222__p × s
22241557782222__q × r
22222237771778__q × s
64484013941778__p × r × 108 + (p × s + q × r) × 104 + q × s
janelinhada minha calculadora comporta no máximo 8 dígitos decimais. Como fazer para multiplicar 6514202 por 9898989?
Felizmente, os três números de que precisamos do lado direito de (A) — a saber p × r, (p × s + q × r) e q × s — podem ser obtidos com apenas três multiplicações. Com efeito, se adotarmos uma nova variável y definida por
y = (p + q) × (r + s),
teremos p × s + q × r = y − p × r − q × s e portanto a equação (A) pode ser reescrita assim:
| u × v = p × r × 10n + ( y − p × r − q × s) × 10n/2 + q × s . | (B) |
É bem verdade que esta equação envolve duas adições e duas subtrações adicionais, mas essas operações consomem muito menos tempo que as multiplicações. Por isso, (B) vale a pena.
Se n não for par, basta trocar n/2 por ⌈n/2⌉ , o que equivale a acrescentar um 0 à esquerda de u e de v. Se denotarmos ⌈n/2⌉ por m, teremos u = p × 10m + q e v = r × 10m + s e portanto
u × v = p × r × 102m + ( y − p × r − q × s) × 10m + q × s ,
Exemplo C: Quero multiplicar 6514202 por 9898989. O resultado das contas pode ser resumido assim:
22222206514202__u = p × 104 + q
22222209898989__v = r × 104 + s
64383929898989__p × r
22222248532222__p + q
22222299782222__r + s
22484232342222__y = (p + q) × (r + s)
22100076172222__z = y − p × r − q × s
22222237771778__q × s
64484013941778__p × r × 108 + z × 104 + q × s
As seguintes observações não afetam o exemplo, mas são relevantes para entender o código que virá a seguir: Se u e v tivessem n dígitos cada, p × r e q × s teriam n+1 dígitos cada, y teria n+2 (mais precisamente, só n+1) dígitos e u × v teria 2n dígitos.
Essas ideias são a base do algoritmo de Karatsuba e Ofman. O algoritmo recebe números naturais u e v com no máximo n dígitos cada e devolve o produto u × v:
| Karatsuba (u, v, n) |
| 11 . se n ≤ 3 |
| 12 .ooo devolva u × v e pare |
| 13 . m := ⌈n/2⌉ |
| 14 . p := ⌊u/10m⌋ |
| 15 . q := u mod 10m |
| 16 . r := ⌊v/10m⌋ |
| 17 . s := v mod 10m |
| 18 . pr := Karatsuba (p, r, m) |
| 19 . qs := Karatsuba (q, s, m) |
| 10 . y := Karatsuba (p + q, r + s, m+1) |
| 11 . uv := pr × 102m + (y − pr − qs) × 10m + qs |
| 12 . devolva uv |
(Observe que a variável pr armazena o produto p × r, a variável qs armazena o produto q × s, e assim por diante.) Na linha 7, v mod 10m é o resto da divisão de v por 10m, ou seja, o número representado pelos últimos m dígitos da expansão decimal de v. Na terminologia do método de divisão e conquista, as linhas 3 a 7 constituem a fase de conquista do algoritmo.
As instâncias em que n vale 1, 2 ou 3 devem ser tratadas na base da recursão porque o algoritmo é aplicado, na linha 10, a uma instância de tamanho ⌈n/2⌉ +1, e este número só é menor que n quando n > 3.
É claro que o algoritmo produz o resultado correto se n ≤ 3. Suponha agora que n > 3. Como m < n, podemos supor, por hipótese de indução, que a linha 8 produz o resultado correto, ou seja, que pr = p × r. Analogamente, podemos supor que qs = q × s, ps = p × s e qr = q × r no início da linha 11. Isso encerra a fase de conquista do algoritmo. A linha 11 não faz mais que implementar (B), que constitui a fase de combinação do algoritmo. Portanto, uv = u × v.
genéricado algoritmo?
Quanto tempo o algoritmo Karatsuba consome? É razoável supor que o consumo de tempo do algoritmo só depende do número de dígitos, n, de u e de v. (Portanto, não há um melhor caso nem um pior caso.) Denote por T(n) o consumo de tempo do algoritmo. Podemos supor que as linhas 1 a 7 do algoritmo consomem n unidades de tempo. Então,
| T(n) = 2 T(⌈n/2⌉) + T(⌈n/2⌉ +1) + n | (C) |
para n = 4, 5, 6, etc. As duas parcelas T(⌈n/2⌉) se referem às linhas 8 e 9. A parcela T(⌈n/2⌉ +1) se refere à linha 10. A parcela n resume o consumo de tempo das demais linhas.
Veja o detalhamento da parcela n da recorrência.
As linhas 1 e 2 consomem 1 uma unidade de tempo cada.
A linha 3 consome 1 uma unidade de tempo
pois pode ser implementada com um shift de 1 bit
da representação binária de n.
A linha 4 consome n/2 unidades de tempo,
pois consiste em um mero shift
do vetor que representa u.
Por razões análogas, as linha 5 a 7 consomem n/2 unidades de tempo cada.
Na linha 10,
o cálculo do argumento p + q
da função consome n/2 unidades de tempo.
Da mesma forma, o cálculo do argumento r + s
da função consome n/2 unidades de tempo.
A linha 11
envolve quatro somas/subtrações e dois shifts,
e portanto consome 6n unidades de tempo.
Resumindo:
o conjunto de todas as operações
que não envolvem chamadas recursivas
consome 9n + 2 unidades de tempo.
Como estamos interessados no
consumo de tempo assintótico,
podemos nos atrever a escrever n
no lugar de 9n + 2
.
Isso explica o termo n da recorrência.
Qual a solução da recorrência (C)? Poderíamos apelar para o Teorema Mestre e concluir que T(n) = Θ(nlg 3). Mas é mais interessante deduzir isso diretamente. Para começar, podemos estudar uma recorrência mais simples, na esperança de que ela tenha uma solução semelhante:
S(n) = 3 S(n/2) + n
para n = 2¹, 2², 2³, … Essa recorrência pode ser desenrolada da seguinte maneira:
| S(n) | = | 3 S(n/2) + n |
| = | 3 (3 S(n/4) + n/2) + n | |
| = | 32 S(n/22) + 3 n/2 + n | |
| = | 33 S(n/23) + 32 n/22 + 31 n/21 + n | |
| = | 3i S(n/2i) + 3i−1 n/2i−1 + ⋅⋅⋅ + 31 n/21 + n |
Quando i atinge lg n, temos S(n/2i) = S(1) = 1 = n/2i. Logo,
| S(n) | = | 3i n/2i + 3i−1 n/2i−1 + ⋅⋅⋅ + 31 n/21 + 30 n/20 |
| = | n ((3/2)i + (3/2)i−1 + ⋅⋅⋅ + (3/2)1 + (3/2)0) | |
| = | n ((3/2)i+1 − 1) / (3/2 − 1) | |
| = | 2 n ((3/2)i+1 − 1) | |
| = | 2i+1 (3/2)i+1 − 2i+1 | |
| = | 3i+1 − 2i+1 | |
| = | 3 × 3i − 2 × 2i | |
| = | 3 × 3lg n − 2 × 2lg n | |
| = | 3n lg 3 − 2n . |
A solução S da versão simplificada da recorrência (C) está, portanto, em Θ(nlg 3). A experiência mostra (e o Torema Mestre confirma) que a solução T da recorrência (C) original também está em
Θ(nlg 3).
Um dos exercício abaixo acaba com as dúvidas que possam ter sobrado.
O número lg 3 fica entre 1.5 e 1.6 e portanto n lg 3 fica entre n √n e n2. Assim, o algoritmo Karatsuba é assintoticamente mais rápido que o algoritmo quadrático usual de multiplicação. Mas, em virtude da constante multiplicativa escondida sob a notação Θ, essa superioridade só se manifesta quando n é maior que algumas centenas.