Algoritmo de Karatsuba

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou seção está a ser traduzido de «Умножение_Карацубы» na Wikipédia em russo. 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.

Assenálio 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 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 n é 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 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



Desde que , a multiplicação dos dois 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 subtracção de não mais que dígitos necessários a não mais que 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 [S.l.: s.n.] 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 [S.l.: s.n.] 211: 169–183. 

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