= Solution
Split two $2^{k+1}$-digit numbers into high and low halves:
$$
x=aB+c,\qquad y=bB+d,
$$
where $B$ is the base raised to $2^k$. Their product is
$$
xy=abB^2+(ad+bc)B+cd.
$$
The <Karatsuba multiplication> identity
$$
ad+bc=(a+c)(b+d)-ab-cd
$$
computes the three required half-size products $ab$, $cd$, and $(a+c)(b+d)$, so
$$
f(k+1)\leq3f(k).
$$
Since $f(0)=1$, induction gives $f(k)\leq3^k$. For $n=2^k$,
$$
3^k=n^{\log_2 3}.
$$
Padding an arbitrary input length to the next power of two changes only the constant, yielding $O(n^\alpha)$ digit multiplications with $\alpha=\log3/\log2$.
Back to article page
