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
dígitos a no máximo:
multiplicações de dígitos simples e a exatamente
quando
é uma potência de 2.
É mais rápido que o método usual de multiplicação longa, que necessita de
multiplicações de um dígito simples.
Por exemplo, seja
.
O cálculo final exato será
e
, respectivamente.
O algoritmo de Toom-Cook é uma generalização mais rápida do algoritmo de Karatsuba. Para
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:
Desde que
, a multiplicação dos números
e
possui desempenho equivalente à ordem quadrática.
Seja
um número de
dígitos, que é igual a
![{\displaystyle X=e_{0}+2e_{1}+\ldots +2^{n-1}e_{n-1},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdb7c1d1e5302a3d02079ce76deb9f88fa614385)
onde
.
Assume-se por simplicidade que
. Escrevendo-se
como
![{\displaystyle X=X_{1}+2^{k}X_{2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f03e0fdc2631e5678b87156199bf016b0744d75)
onde
![{\displaystyle X_{1}=e_{0}+2e_{1}+\ldots +2^{k-1}e_{k-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0d2364b0d0ef77cf10bec6a589e0bf653dda28a)
e
![{\displaystyle X_{2}=e_{k}+2e_{k+1}+\ldots +2^{k-1}e_{n-1},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9cf3b7dbfcdd9435bef8a069fedc7a057a411170)
então calculando
, 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8636a6b7f5988056a2a51758202580b81d4b5e42)
e
possuem
dígitos.
podem ter no máximo até
dígitos. Neste caso, serão representados como
, onde
é um número de
dígitos e
é 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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3ef87a75a774a8d8b6636a8f76087aa4bbc94c1)
Seja
o número de operações suficiente para a construção de
dígitos ao quadrado pela fórmula (1). Percebe-se que de (1) prossegue a desigualdade em
:
,
onde
é uma constante em valor absoluto. Na verdade, o lado direito de (1) contém a soma de três quadrados de
dígitos,
, que para serem calculados necessitam de
operações.
Todos os outros cálculos no lado direito de (1), a saber, são a multiplicação por
, cinco adições e uma subtração de no máximo
dígitos necessários a no máximo
operações. Disto resulta (2). Aplicando (2) sucessivamente para
![{\displaystyle \varphi (n2^{-1}),\;\varphi (n2^{-2}),\;\ldots ,\;\varphi (n2^{-m+1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3297baa705ceab45ee5cecf37e13cb499206094)
e tendo em conta que
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 }](https://wikimedia.org/api/rest_v1/media/math/render/svg/99994c727969133daefa09715a676ff23ce97cf4)
![{\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=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd5bd61ba916d9cc1064e6ba2b07f8b2ecc20e9e)
![{\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)=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66c5df1654ac51d7b0d9b6161931c1705f88c66b)
![{\displaystyle =3^{m}+2cn\left(\left({\frac {3}{2}}\right)^{m}-1\right)<3^{m}(2c+1)=(2c+1)n^{\log _{2}3}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93bb176b1d49f4eabb440471bea1049f8e14737d)
Assim, para um número de
operações, suficientes para a construção de
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 }](https://wikimedia.org/api/rest_v1/media/math/render/svg/376269e95284d487c5d2edaf9c79c796b76aac8c)
Se
não for uma potência de dois, então haverá um número inteiro de
dígitos especificando as desigualdades
, expressando
como um número de
dígitos, isto é, deixando
símbolos iguais a zero à esquerda:
![{\displaystyle e_{n}=\ldots =e_{2^{m}-1}=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d3040cbdab34982d0897542051c9e61c31fad75)
Todos os outros argumentos válidos para
produzem a mesma cota superior ligada a essa ordem de
.
Referências
- ↑ A. Karatsuba and Yu. Ofman (1962). Translation in Physics-Doklady, 7 (1963), pp. 595–596. «Multiplication of Many-Digital Numbers by Automatic Computers». Proceedings of the USSR Academy of Sciences. 145: 293–294
- ↑ A. A. Karatsuba (1995). translation from Trudy Mat. Inst. Steklova, 211, 186–202 (1995). «The Complexity of Computations» (PDF). Proceedings of the Steklov Institute of Mathematics. 211: 169–183
Ver também
|
---|
Princípios gerais | |
---|
Áreas | |
---|
Conceitos-chave | |
---|
Conceitos avançados | |
---|
Principais teóricos | |
---|
Categoria Wikibook |