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.^[1][2] Este algoritmo reduz a multiplicação de dois números de ${\displaystyle n}$ dígitos a no máximo:

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

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

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

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

O algoritmo de Toom-Cook é uma generalização mais rápida do algoritmo de Karatsuba. Para ${\displaystyle 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:

${\displaystyle (a+bx)^{2}=a^{2}+((a+b)^{2}-a^{2}-b^{2})x+b^{2}x^{2}.}$

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

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

${\displaystyle X=e_{0}+2e_{1}+\ldots +2^{n-1}e_{n-1},}$

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

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

${\displaystyle X=X_{1}+2^{k}X_{2},}$

onde

${\displaystyle X_{1}=e_{0}+2e_{1}+\ldots +2^{k-1}e_{k-1}}$

e

${\displaystyle X_{2}=e_{k}+2e_{k+1}+\ldots +2^{k-1}e_{n-1},}$

então calculando ${\displaystyle X^{2}}$, fica como

${\displaystyle 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)}$

${\displaystyle X_{1}}$ e ${\displaystyle X_{2}}$ possuem ${\displaystyle k}$ dígitos. ${\displaystyle X_{1}+X_{2}}$ podem ter no máximo até ${\displaystyle k+1}$ dígitos. Neste caso, serão representados como ${\displaystyle 2X_{3}+X_{4}}$, onde ${\displaystyle X_{3}}$ é um número de ${\displaystyle k}$ dígitos e ${\displaystyle X_{4}}$ é um número de um único dígito. Então

${\displaystyle (X_{1}+X_{2})^{2}=4X_{3}^{2}+4X_{3}X_{4}+X_{4}^{2}.}$

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

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

onde ${\displaystyle c>0}$ é uma constante em valor absoluto. Na verdade, o lado direito de (1) contém a soma de três quadrados de ${\displaystyle k}$ dígitos, ${\displaystyle k=n2^{-1}}$, que para serem calculados necessitam de ${\displaystyle 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 ${\displaystyle 4,\;2^{k},\;2^{n}}$, cinco adições e uma subtração de no máximo ${\displaystyle 2n}$ dígitos necessários a no máximo ${\displaystyle n}$ operações. Disto resulta (2). Aplicando (2) sucessivamente para

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

e tendo em conta que

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

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

${\displaystyle \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=}$

${\displaystyle =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)=}$

${\displaystyle =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 ${\displaystyle \varphi (n)}$ operações, suficientes para a construção de ${\displaystyle n}$ dígitos ao quadrado pela fórmula (1), a estimativa será de:

${\displaystyle \varphi (n)<(2c+1)n^{\log _{2}3},\quad \log _{2}3=1{,}5849\ldots }$

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

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

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

Referências

Ver também

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