Quanto tempo é necessário para multiplicar dois números naturais (como 3141592653589793238462643383 e 1414213562373095048801688724209, por exemplo)? Se os números têm m e n dígitos respectivamente, o algoritmo usual consome tempo proporcional a mn. No caso m = n, o consumo de tempo é, portanto, proporcional a n2.
É difícil imaginar um algoritmo mais rápido que o usual se m e n forem pequenos (menores que 500, digamos). Mas existe um algoritmo que é bem mais rápido quando m e n são grandes (como acontece em criptografia, por exemplo).
Veja o capítulo 1 de MS. Veja também as seções 2.7.3 e 7.1 de BB e a seção 5.5 de KT.
Usaremos notação decimal para representar números naturais. Diremos que um dígito é qualquer número natural menor que 10. Diremos que um número natural u tem no máximo n dígitos se u < 10n.
Problema da multiplicação: Dados números naturais u e v com no máximo n dígitos cada, calcular (a expansão decimal d)o produto uv.
O algoritmo de Karatsuba e Ofman resolve o problema em Θ(nlg 3) unidades de tempo. (Observe que lg 3 fica entre 1,5 e 1,6.) A função nlg 3 é solução da recorrência T(n) = 3 T(⌈n/2⌉) + n (veja a definição de teto).
Veja mais nas páginas 37 a 42 do meu livrinho Minicurso de Análise de Algoritmos e nas página 45 a 57 dos slides que acompanham o livrinho.
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. Assim,
u = p 10n/2 + q .
Defina r e s analogamente para v, de modo que v = r 10n/2 + s. Teremos então
| uv = pr 10n + (ps+qr) 10n/2 + qs . | (*) |
Esta expressão reduz a multiplicação de dois números com no máximo n dígitos cada a quatro multiplicações (a saber, p por r, p por s, q por r e q por s) de números com no máximo n/2 dígitos cada. Infelizmente, essa redução não é suficiente para tornar a multiplicação mais eficiente.
Agora observe que os três números de que precisamos do lado direito de (*) — a saber pr, (ps+qr) e qs — podem ser obtidos com apenas três multiplicações, pois
ps + qr = y − pr − qs , sendo y = (p+q)(r+s),
e portanto a equação (*) pode ser substituída por
uv = pr 10n + ( y − pr − qs) 10n/2 + qs .
(É 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.) Se n não é par, basta trocar n/2 por k = ⌈n/2⌉. Teremos então u = p 10k + q e v = r 10k + s e portanto
uv = pr 102k + ( y − pr − qs) 10k + qs .
Esta é a base do algoritmo.
Exemplo: Quero multiplicar 6514202 por 9898989. O resultado das contas pode ser resumido assim:
22222226514202__u = p104 + q
22222229898989__v = r104 + s64383929898989__pr
22222237771778__qs22222248532222__p+q
22222299782222__r+s
22484232342222__y = (p+q)(r+s)
22100076172222__y−pr−qs
64484013941778__uv = pr108 + (y−pr−qs)104 + qs
| Karatsuba-Ofman (u, v, n) |
| 11 _ se n ≤ 3 |
| 12 ____ então devolva u · v |
| 13 ____ senão m ← ⌈n/2⌉ |
| 14 ____ senão p ← ⌊u/10m⌋ |
| 15 ____ senão q ← u mod 10m |
| 16 ____ senão r ← ⌊v/10m⌋ |
| 17 ____ senão s ← v mod 10m |
| 18 ____ senão pr ← Karatsuba-Ofman (p, r, m) |
| 19 ____ senão qs ← Karatsuba-Ofman (q, s, m) |
| 10 ____ senão y ← Karatsuba-Ofman (p+q, r+s, m+1) |
| 11 ____ senão x ← pr · 102m + (y − pr − qs) · 10m + qs |
| 12 ____ senão devolva x |