TAOCP 4.3.3 Exercise 13
Let $T(n)$ denote the time needed to multiply two $n$-bit numbers by one of the fast multiplication methods discussed in this section.
Section 4.3.3: How Fast Can We Multiply?
Exercise 13. [M25] What is a good upper bound on the time needed to multiply an $m$-bit number by an $n$-bit number, when both $m$ and $n$ are very large but $n$ is much larger than $m$, based on the results discussed in this section for the case $m = n$?
Verified: yes
Solve time: 1m16s
Solution
Let $T(n)$ denote the time needed to multiply two $n$-bit numbers by one of the fast multiplication methods discussed in this section. By Theorem A, for every $\epsilon>0$ there exists an algorithm such that
$$ T(n) < c(\epsilon)n^{1+\epsilon}. \eqno(11) $$
Suppose now that $m$ and $n$ are very large and that $m\ll n$. Write the $n$-bit number $v$ in base $2^m$:
$$ v=V_t2^{tm}+V_{t-1}2^{(t-1)m}+\cdots+V_1 2^m+V_0, $$
where each $V_j$ has at most $m$ bits, and where
$$ t+1=\left\lceil\frac{n}{m}\right\rceil . $$
Then
$$ uv = \sum_{j=0}^{t}(uV_j)2^{jm}. $$
Each product $uV_j$ is the product of two numbers having at most $m$ bits. Hence all of these products can be computed in time
$$ (t+1)T(m). $$
The remaining work consists of shifts and additions of numbers having at most $m+n$ bits. There are $t+1$ shifted products, so the total cost of combining them is
$$ O((t+1)n) = O!\left(\frac{n^2}{m}\right). $$
Therefore
$$ M(m,n) = O!\left(\frac{n}{m}T(m)+\frac{n^2}{m}\right), $$
where $M(m,n)$ denotes the time to multiply an $m$-bit number by an $n$-bit number.
Using (11),
$$ M(m,n) = O!\left(\frac{n}{m}m^{1+\epsilon}+\frac{n^2}{m}\right) = O!\left(nm^{\epsilon}+\frac{n^2}{m}\right). $$
A better bound is obtained by applying the polynomial method asymmetrically. Let
$$ v=V(2^m) $$
with degree approximately $n/m$, while $u$ is regarded as a constant coefficient. Evaluating and interpolating a polynomial of degree $O(n/m)$ requires only a number of operations proportional to $n/m$, and each multiplication involved is a multiplication of an $m$-bit number by another quantity of the same order. Consequently the dominant cost is proportional to
$$ \frac{n}{m}T(m). $$
Substituting (11) gives
$$ M(m,n) = O!\left(\frac{n}{m}m^{1+\epsilon}\right) = O(nm^{\epsilon}). $$
Since $\epsilon$ may be chosen arbitrarily small, the multiplication of an $m$-bit number by an $n$-bit number can be performed in essentially linear time in the larger operand:
$$ M(m,n) < c(\epsilon), n, m^{\epsilon}. $$
Thus a good upper bound, based on the methods of this section, is
$$ \boxed{M(m,n)=O!\left(n,m^{\epsilon}\right)\qquad(\epsilon>0).} $$
For fixed $m$ this becomes $O(n)$, and when $m\ll n$ it is substantially smaller than the bound obtained by treating both operands as $n$-bit numbers. ∎