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