Algoritmo de Karatsuba

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido de ru:Умножение_Карацубы. Ajude e colabore com a tradução.
Ambox grammar.svg
Esta página ou secção precisa de correção ortográfico-gramatical.
Pode conter incorreções textuais, podendo ainda necessitar de melhoria em termos de vocabulário ou coesão, para atingir um nível de qualidade superior conforme o livro de estilo da Wikipédia. Se tem conhecimentos linguísticos, sinta-se à vontade para ajudar.



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 19621 2 . 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[editar | editar código-fonte]


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.

Referências

  1. A. Karatsuba and Yu. Ofman. (1962). "Multiplication of Many-Digital Numbers by Automatic Computers". Proceedings of the USSR Academy of Sciences 145: 293–294.
  2. A. A. Karatsuba. (1995). "The Complexity of Computations". Proceedings of the Steklov Institute of Mathematics 211: 169–183.

Veja também[editar | editar código-fonte]