# 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

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.

## Feedback

Question? Comment? Contact me