Karatsuba multiplication

Multiplying two $$n$$-bit integers with the naive algorithm takes $$\Theta(n^2)$$ time. But it can be done faster – with the Karatsuba algorithm it takes $$\Theta(n^{\log_2 3}) \approx \Theta(n^{1.58})$$ time, which gives a significant speed-up for large numbers.

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

1. Select a modulus $$m \in \mathbb{N}^+$$. Any number would work, but it’s most efficient to choose a power of 2 that is near $$\sqrt{x}$$. This lets the modulo and divide be realized as bit masking and right shifting, and ensures the split is as balanced as possible.
2. Let $$x_\text{low} = x \text{ 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 \text{ 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$$.

Note that in steps 4 through 6, we perform Karatsuba multiplication recursively as long as the numbers are above a certain size.

Benchmark

The time to multiply two n-bit integers with naive multiplication versus Karatsuba multiplication was measured and graphed. For example, for n = 107 bits, naive multiplication took 1079 seconds while Karatsuba multiplication took 39 seconds, implying a 28× speed-up. Karatsuba multiplication starts to be faster than naive multiplication at around n = 3000 bits.

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.

Older versions of Java (SE 7 and below) used the $$\Theta(n^2)$$ naive algorithm for BigInteger.multiply(), so the code offered on this page would achieve an improvement in speed. But Java SE 8 introduced an implementation of Karatsuba multiplication and Toom-Cook multiplication, and uses these faster algorithms appropriately when operating on longer numbers. So the benchmark results on this page are only valid for Java SE 7 and below. To perform benchmarking on Java SE 8 and above, you would need to manually reimplement the naive multiplication or copy the Java standard library’s implementation while stripping out the faster algorithms.