Karatsuba Integer Multiplication

Problem

Problem. Given two positive $n$-bit integers $x$ and $y$, compute their product $xy$.

The elementary school algorithm runs in $O(n^2)$. Our goal is a subquadratic algorithm.

Note: Efficiency is measured with respect to the input size (number of bits). $O(PQ)$ is exponential in the input size.

Divide-and-Conquer Approach

Split $x = x_1 \cdot 2^{\lfloor n/2 \rfloor} + x_0$ and $y = y_1 \cdot 2^{\lfloor n/2 \rfloor} + y_0$:

\[xy = x_1 y_1 \cdot 2^{2\lfloor n/2 \rfloor} + (x_1 y_0 + x_0 y_1) \cdot 2^{\lfloor n/2 \rfloor} + x_0 y_0\]

4-recursion version:

p1 ← Multiply(x1, y1)
p2 ← Multiply(x1, y0)
p3 ← Multiply(x0, y1)
p4 ← Multiply(x0, y0)
return p1·2^(2⌊n/2⌋) + (p2+p3)·2^(⌊n/2⌋) + p4

Theorem 1. $T(n) = 4T(n/2) + \Theta(n) = \Theta(n^2)$ — no improvement over the elementary algorithm.

Karatsuba Algorithm

Key observation: $x_1 y_0 + x_0 y_1 = (x_1 + x_0)(y_1 + y_0) - x_1 y_1 - x_0 y_0$

This reduces 4 multiplications to 3.

function Multiply(x, y):
    if n ≤ 3: return elementary_school(x, y)
    p1 ← Multiply(x1+x0, y1+y0)
    p2 ← Multiply(x1, y1)
    p3 ← Multiply(x0, y0)
    return p2·2^(2⌊n/2⌋) + (p1-p2-p3)·2^(⌊n/2⌋) + p3

Theorem 2 (Correctness). Proved by induction on $n$:

\[p_2 \cdot 2^{2\lfloor n/2 \rfloor} + (p_1 - p_2 - p_3) \cdot 2^{\lfloor n/2 \rfloor} + p_3 = xy\]

Theorem 3 (Time complexity). The Karatsuba algorithm runs in $O(n^{\log_2 3})$ time.

Proof. $T(n) = 3T(n/2) + cn$. By the Master Theorem:

\[T(n) = \Theta(n^{\log_2 3}) = O(n^{1.59}) \qquad \square\]