Algoritmo de Karatsuba

Predefinição:Mais notas 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}),{\log }_{2}3=1,5849\dots$ 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+\dots +2^{n-1}{e}_{n-1},$

onde $e_j\in 0,1,j=0,1,\dots ,n-1$.

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

$X=X_1+2^k{X}_2,$

onde

$X_1=e_0+2e_1+\dots +2^{k-1}{e}_{k-1}$

e

$X_2=e_k+2e_{k+1}+\dots +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.(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 $\phi (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 $\phi (n)$:

$\phi (n)⩽3\phi (n{2}^{-1})+cn,(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=n{2}^{-1}$, que para serem calculados necessitam de $3\phi (m)=3\phi (n{2}^{-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

$\phi (n{2}^{-1}),\phi (n{2}^{-2}),\dots ,\phi (n{2}^{-m+1})$

e tendo em conta que

$\phi (n{2}^{-m})=\phi (1)=1,$ obtemos

$\phi (n)⩽3(3\phi (n{2}^{-2})+cn{2}^{-1})+cn=3^2\phi (n{2}^{-2})+3c(n{2}^{-1})+cn⩽\dots ⩽$

$⩽3^m\phi (n{2}^{-m})+3^{m-1}c(n{2}^{-m+1})+3^{m-2}c(n{2}^{-m+2})+\dots +3c(n{2}^{-1})+cn=$

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

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

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

$\phi (n)<(2c+1)n^{{\log }_{2}3},{\log }_{2}3=1,5849\dots$

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⩽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=\dots =e_{2^m-1}=0.$

Todos os outros argumentos válidos para $\phi (n)$ produzem a mesma cota superior ligada a essa ordem de $n$. Predefinição:Referências

Ver também

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