Algoritmo de Karatsuba

Algoritmo de Karatsuba ou Método de Multiplicação de Karatsuba é um método para multiplicar números grandes eficientemente, descoberto por Anatolii Alexeievitch Karatsuba em 1960 e publicado en 1962 . Este algoritmo reduz a multiplicação de dois números de $n$ dígitos a no máximo :

$M(n)=O(n^{\log_23}),\quad\log_23=1{,}5849\ldots$ multiplicações de dígitos simples e a exatamente $n^{\log_23}$ quando n é uma potência de 2).

É mais rápido que o método usual de multiplicação longa, que necessita de $n^2$ multiplicações de um dígito simples.

Por exemplo, seja $n = 2^{10} = 1024$.

O cálculo final exato será $3^{10} = 59.049$ e $(2^{10})^2 = 1.048.576$, respectivamente.

O algoritmo de Toom-Cook é uma generalização mais rápida do algoritmo de Karatsuba. Para $n$ suficientemente grande, o algoritmo de Schönhage-Strassen é melhor que o algoritmo de Karatsuba.

O algoritmo de Karatsuba é um exemplo de algoritmo do tipo divisão e conquista, e do modelo de algoritmo de partición binaria. A classificação de algoritmos do tipo divisão e conquista foi usada pela primeira vez para este método.

Algoritmo

A demonstração será feita por fórmulas. Seja a igualdade

$(a+bx)^2=a^2+((a+b)^2-a^2-b^2)x+b^2x^2.$

Desde que $4ab=(a+b)^2-(a-b)^2$, a multiplicação dos dois números $a$ e $b$ possui desempenho equivalente à ordem quadrática.

Seja $X$ um número de $n$ dígitos, que é igual a

$X=e_0+2e_1+\ldots+2^{n-1}e_{n-1},$

onde $e_j\in{0,\;1},\;j=0,\;1,\;\ldots,\;n-1$.

Assume-se por simplicidade que $n=2^m,\;m\geqslant 1;\;n=2k$. Escrevendo-se $X$ como

$X=X_1+2^kX_2,$

onde

$X_1=e_0+2e_1+\ldots+2^{k-1}e_{k-1}$

e

$X_2=e_k+2e_{k+1}+\ldots+2^{k-1}e_{n-1},$

então calculando $X^2$ fica como

$X^2=(X_1+2^kX_2)^2=X_1^2+((X_1+X_2)^2-(X_1^2+X_2^2))2^k+X_2^22^n.\qquad(1)$

$X_1$ e $X_2$ possuem $k$ dígitos. $X_1+X_2$ podem ter no máximo até $k+1$ dígitos. Neste caso, serão representados como $2X_3+X_4$, onde $X_3$ é um número de $k$ dígitos e $X_4$ é um número de um único dígito. Então

$(X_1+X_2)^2=4X_3^2+4X_3X_4+X_4^2.$

Seja $\varphi(n)$ o número de operações suficiente para a construção de $n$ dígitos ao quadrado pela fórmula (1). Percebe-se que de (1) prossegue a desigualdade em $\varphi(n)$:

$\varphi(n)\leqslant 3\varphi(n2^{-1})+cn,\qquad(2)$,

onde $c>0$ é uma constante em valor absoluto. Na verdade, o lado direito de (1) contém a soma de três quadrados de $k$ dígitos, $k=n2^{-1}$, que para serem calculados necessitam de $3\varphi(m)=3\varphi(n2^{-1})$ operações.

Todos os outros cálculos no lado direito de (1), a saber são a multiplicação por $4,\;2^k,\;2^n$, cinco adições e uma subtracção de não mais que $2n$ dígitos necessários a não mais que $n$ operações. Disto resulta (2). Aplicando (2) sucessivamente para

$\varphi(n2^{-1}),\;\varphi(n2^{-2}),\;\ldots,\;\varphi(n2^{-m+1})$

e tendo em conta que

$\varphi(n2^{-m})=\varphi(1)=1,$ obtemos

$\varphi(n)\leqslant 3(3\varphi(n2^{-2})+cn2^{-1})+cn=3^2\varphi(n2^{-2})+3c(n2^{-1})+cn\leqslant\ldots\leqslant$

$\leqslant 3^m\varphi(n2^{-m})+3^{m-1}c(n2^{-m+1})+3^{m-2}c(n2^{-m+2})+\ldots+3c(n2^{-1})+cn=$

$=3^m+cn\left(\left(\frac{3}{2}\right)^{m-1}+\left(\frac{3}{2}\right)^{m-2}+\ldots+\left(\frac{3}{2}\right)+1\right)=$

$=3^m+2cn\left(\left(\frac{3}{2}\right)^m-1\right)<3^m(2c+1)=(2c+1)n^{\log_23}.$

Assim, para um número de $\varphi(n)$ operações, suficientes para a construção de $n$ dígitos ao quadrado pela fórmula (1) a estimativa será de:

$\varphi(n)<(2c+1)n^{\log_23},\quad \log_23=1{,}5849\ldots$

Se $n$ não for uma potência de dois, então haverá um número inteiro de $m$ dígitos especificando as desigualdades $2^{m-1}<n\leqslant 2^m$, expressando $X$ como um número de $2^m$ dígitos, isto é, deixando $2^m-n$ símbolos iguais a zero à esquerda:

$e_n=\ldots=e_{2^m-1}=0.$

Todos os outros argumentos válidos para $\varphi(n)$ produzem a mesma cota superior ligada a essa ordem de $n$.

Veja também

• Algoritmo de Dijkstra
• Autômato
• Máquina de Moore
• Máquina de Turing
• Turmites
• Vida artificial