Karatsuba algorithm
Algoritmo de Karatsuba
- Date
- 1960 · confidence high
- Place
- Moscow, Russia
- Credited to
- Anatoly Karatsuba
- Field
- Knowledge & symbols
What it is
A fast multiplication algorithm for large numbers that reduces an n-digit multiplication to three (n/2)-digit multiplications, the first method to beat the quadratic complexity of the traditional algorithm.
What it led to
- the first multiplication algorithm faster than the classical method
- later divide-and-conquer algorithms (Toom-Cook, Schönhage-Strassen)
- use in arbitrary-precision arithmetic software
- a boost to computational complexity theory