# 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:

- 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 even as possible.
- 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}\).
- 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}\).
- Let \(a = x_\text{high} y_\text{high}\).
- Let \(b = (x_\text{low} + x_\text{high})(y_\text{low} + y_\text{high})\).
- Let \(c = x_\text{low} y_\text{low}\).
- 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` = 10^{7} 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.

## Source code

- Java implementation: KaratsubaMultiplication.java
- Python implementation: karatsuba.py