= Solution
A <divide-and-conquer algorithm> handles small base cases directly, divides a larger instance into smaller instances of the same problem, solves them recursively, and combines their answers. The savings come from the number and sizes of recursive calls and the combination cost.
For <Karatsuba multiplication>, split the $n$-bit inputs as $x=aB+b$, $y=cB+d$, where $B=2^k$ and $k=\lceil n/2\rceil$. Compute only three recursive products:
$$
p=ac,\qquad q=bd,\qquad r=(a-b)(c-d).
$$
Then the <Karatsuba three-product identity> gives
$$
\boxed{xy=pB^2+(p+q-r)B+q.}
$$
The absolute differences have at most $k$ bits; multiply their magnitudes and restore the sign of $r$. Additions, subtractions and shifts cost $O(n)$ bit operations. With constant-size base cases, the <recurrence relation> is $T(n)=3T(\lceil n/2\rceil)+O(n)$, giving \b[$O(n^{\log_2 3})$] by the <Master theorem>. The difference-product version avoids an extra carry bit in the recursive operands.
Back to article page
