Karatsuba Algorithm

Karatsuba algorithm is a fast multiplication algorithm with time complexity $O(n^{\log_2 3}) \approx O(n^{1.58})$.

The basic idea is divide-and-conquer:

$x = x_H \cdot r^{n / 2} + x_L \\ y = y_H \cdot r^{n / 2} + y_L \\ xy = x_H y_H \cdot r^n + (x_H y_L + x_L y_H) \cdot r^{n / 2} + x_L y_L \\$

This requires 4 multiplications each step, which doesn’t improve the time complexity. The insight is:

$x_H y_L + x_L y_H = (x_H + x_L) (y_H + y_L) - x_H y_H - x_L y_L \\$

This requires 3 multiplications instead of 4 each step and reduces time complexity from $O(n^2)$ to $O(n^{\log_2 3})$.

Reference