Algoritmo de Karatsuba
De Wikipedia, a enciclopédia encyclopedia
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.