Algoritmo de Karatsuba
Karatsuba algorithm
- Fecha
- 1960 · fiabilidad alta
- Lugar
- Moscú, Rusia
- Autoría
- Anatoly Karatsuba
- Ámbito
- Saber y símbolos
Qué es
Algoritmo de multiplicación rápida de números grandes que reduce una multiplicación de n dígitos a tres multiplicaciones de n/2 dígitos, superando por primera vez la complejidad cuadrática del método tradicional.
A qué dio paso
- primer algoritmo de multiplicación más rápido que el método clásico
- algoritmos divide y vencerás posteriores (Toom-Cook, Schönhage-Strassen)
- uso en aritmética de precisión arbitraria en software
- impulso a la teoría de la complejidad computacional