O algoritmo Karatsuba é um algoritmo de multiplicação rápida. Foi descoberto por Anatolii Alexeevitch Karatsuba em 1960 e publicado em 1962. Que reduz a multiplicação de dois números de n dígitos no máximo 3 n^{\log_23}\approx 3 n^{1.585}.
Este algoritmo tem aplicações diversas na área da programação linear inteira, um deles é o produto de duas matrizes, conhecido por algoritmo de Strassen
No hay comentarios:
Publicar un comentario