Algoritmo de Karatsuba

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

$M(n)=O(n^{\log _{2}3}),\quad \log _{2}3=1{,}5849\ldots$ multiplicações de dígitos simples e a exatamente $n^{\log _{2}3}$ 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 partição binária. 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^{2}x^{2}.$

Desde que $4ab=(a+b)^{2}-(a-b)^{2}$, a multiplicação dos 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^{k}X_{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^{k}X_{2})^{2}=X_{1}^{2}+((X_{1}+X_{2})^{2}-(X_{1}^{2}+X_{2}^{2}))2^{k}+X_{2}^{2}2^{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_{3}X_{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 subtração de no máximo $2n$ dígitos necessários a no máximo $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 _{2}3}.$

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 _{2}3},\quad \log _{2}3=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$.

Ver também

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