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

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 .

Ver também

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

Categoria:Algoritmos