Karatsuba

Karatsuba's algorithm is a fast multiplication method for large integers. It was discovered in 1960 by Anatolii A. Karatsuba and Sergei Ofman while working at the Moscow Institute. The algorithm reduces the number of recursive multiplications required when multiplying two integers, offering a significant improvement over the traditional grade-school approach for sufficiently large numbers.

Idea: express each number in base B as x = a1 B^m + a0 and y = b1 B^m + b0, where m is chosen so that the parts have roughly half the digits. A direct multiplication would compute four products a1*b1, a1*b0, a0*b1, a0*b0. Karatsuba's trick computes z2 = a1*b1 and z0 = a0*b0, and z1 = (a1 + a0)*(b1 + b0) - z2 - z0. Then x*y = z2 B^{2m} + z1 B^m + z0. This uses only three multiplications of half-size numbers plus some additions and subtractions.

Complexity: The recurrence T(n) = 3 T(n/2) + O(n) yields T(n) = O(n^{log2 3}) ≈ O(n^{1.585}). This beats the naive O(n^2) multiplication, which makes Karatsuba advantageous for moderately large operands. However, the constant factors and overhead mean it is not always faster for small inputs.

In practice, Karatsuba is used in many arbitrary-precision arithmetic libraries and computer algebra systems. It forms the basis of many divide-and-conquer multiplication strategies and has been extended or superseded by more advanced methods for very large numbers, such as Toom-Cook and Schönhage-Strassen (FFT) multiplication. The algorithm is widely taught as a fundamental example of a fast, recursive multiplication technique.