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 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 editar

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

 


onde  .

Assume-se por simplicidade que  . Escrevendo-se   como

 


onde

 


e

 


então calculando  , fica como

 


  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

 

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

 


e tendo em conta que

  obtemos
 


 
 


 


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:

 


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:

 


Todos os outros argumentos válidos para   produzem a mesma cota superior ligada a essa ordem de  .

Referências

  1. 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 
  2. 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 editar