Karatsuba multiplication

Multiplying two \(n\)-bit integers with the naïve algorithm uses \(O(n^2)\) time. Doing it with the Karatsuba algorithm uses \(O(n^{\log_3 2}) \approx O(n^{1.58})\) time.

The Karatsuba multiplication algorithm for integers \(x\) and \(y\) is based on the following observations:

  1. Select a modulus \(m\). For binary arithmetic, we choose this to be a power of 2.
  2. Let \(x_\text{low} = x \mod{m}\) and \(x_\text{high} = \lfloor x / m \rfloor\). We have \(x = m x_\text{high} + x_\text{low}\).
  3. Let \(y_\text{low} = y \mod{m}\) and \(y_\text{high} = \lfloor y / m \rfloor\). We have \(y = m y_\text{high} + y_\text{low}\).
  4. Let \(a = x_\text{high} y_\text{high}\).
  5. Let \(b = (x_\text{low} + x_\text{high})(y_\text{low} + y_\text{high})\).
  6. Let \(c = x_\text{low} y_\text{low}\).
  7. Then \(xy = am^2 + (b - a - c)m + c\).

Benchmark

Benchmark graph

The time to multiply two \(n\)-bit integers with naïve multiplication versus Karatsuba multiplication was measured and graphed. For example, for \(n = 10^7\), naïve multiplication took 1079 seconds while Karatsuba multiplication took 39 seconds. Karatsuba multiplication starts being noticeably faster than naïve multiplication at around \(n = 3000\).

The tests were performed on Intel Core 2 Quad Q6600 (2.40 GHz) using a single thread, Windows XP SP 3, Java 1.6.0_22.

Code