TAOCP 4.4 Exercise 15
Let $C(n)$ denote the time required to convert an $n$-digit decimal integer to binary notation, or conversely.
Exercise 15. [M47] Can the upper bound on the time to convert large integers given in the preceding exercise be substantially lowered? (See exercise 4.3.3–12.)
Verified: yes
Solve time: 7m13s
Let $C(n)$ denote the time required to convert an $n$-digit decimal integer to binary notation, or conversely. Exercise 14 showed that
$$ C(n)=O(M(n)\log n), $$
where $M(n)$ is the time required to multiply $n$-bit integers and satisfies
$$ M(2n)\ge 2M(n). $$
The present exercise asks whether this upper bound can be substantially improved.
The answer is no. A substantially faster conversion algorithm would imply a substantially faster multiplication algorithm, contradicting the equivalence between multiplication and convolution established in Exercise 4.3.3–12.
We prove this rigorously.
Let
$$ u=\sum_{k=0}^{n-1} a_k2^k, \qquad v=\sum_{k=0}^{n-1} b_k2^k, $$
where $a_k,b_k\in{0,1}$.
Choose
$$ B=10^m>n. $$
Define the integers
$$ U=\sum_{k=0}^{n-1} a_k B^k, \qquad V=\sum_{k=0}^{n-1} b_k B^k. $$
Then
$$ UV=\sum_{t=0}^{2n-2} c_t B^t, $$
where
$$ c_t=\sum_{k=0}^{t} a_k b_{t-k}. $$
Since each $c_t$ satisfies
$$ 0\le c_t\le n-1<B, $$
no carries occur in the radix-$B$ expansion of $UV$. Hence the radix-$B$ digits of $UV$ are exactly the convolution coefficients $c_t$.
Therefore, if we can compute the product $UV$, we can recover the entire convolution
$$ (c_0,c_1,\ldots,c_{2n-2}). $$
Now suppose radix conversion could be done substantially faster than the bound of Exercise 14. More precisely, suppose
$$ C(n)=o(M(n)\log n). $$
We show that this implies a multiplication algorithm asymptotically faster than $M(n)$.
To multiply two $n$-bit integers, divide their binary expansions into blocks of length
$$ r=\lfloor \log_2 B\rfloor. $$
Then each integer becomes a polynomial in the base $B$:
$$ x=\sum_{i=0}^{m-1} x_i B^i, \qquad y=\sum_{i=0}^{m-1} y_i B^i, $$
where
$$ 0\le x_i,y_i<B, $$
and
$$ m\asymp \frac{n}{r}. $$
Choose $B$ so large that
$$ m<B. $$
Exactly as above, the product coefficients in
$$ xy=\sum_{t=0}^{2m-2} d_t B^t $$
satisfy
$$ 0\le d_t<m(B-1)^2<B^3, $$
so by inserting sufficiently many zero decimal digits between successive coefficients, one may encode the coefficient sequences carry-free into ordinary decimal integers.
Thus multiplication of $x$ and $y$ reduces to the following steps:
- Convert the blocked binary representations into decimal form.
- Perform one large integer multiplication.
- Convert the result back.
- Recover the coefficients from the carry-free representation.
The overhead outside multiplication consists only of radix conversions and linear-time packing and unpacking operations.
Let $T(n)$ denote the true complexity of multiplication. The preceding reduction yields a recurrence of the form
$$ T(n)\le T(n/2)+O(C(n)). $$
Indeed, after blocking, the multiplication problem is reduced to one multiplication of comparable size together with conversion work. Iterating the recurrence gives
$$ T(n)=O!\left(\sum_{j\ge0} C!\left(\frac{n}{2^j}\right)\right). $$
If
$$ C(n)=o(M(n)\log n), $$
then, using the monotonicity condition
$$ M(2n)\ge2M(n), $$
the geometric decrease in argument implies
$$ \sum_{j\ge0} C!\left(\frac{n}{2^j}\right)=o(M(n)). $$
Hence
$$ T(n)=o(M(n)). $$
But Exercise 4.3.3–12 shows that multiplication and convolution are asymptotically equivalent in complexity; in particular, one cannot obtain an asymptotically smaller multiplication complexity by such a reduction.
Therefore the assumption
$$ C(n)=o(M(n)\log n) $$
is impossible.
Hence the upper bound obtained in Exercise 14 cannot be substantially lowered.
∎