Karatsuba algorithm

Summary

The Karatsuba algorithm multiplies two $n$-digit integers with $O(n^{\log_2 3})$ digit operations, and $\log_2 3 \approx 1.585$. It splits each factor into two halves and gets the product from three half-size products instead of the four of the obvious method. It was the first method to beat the $O(n^2)$ cost of schoolbook multiplication, and it is a standard example of a divide-and-conquer algorithm. The same trick multiplies polynomials.