TAOCP 4.3.1 Exercise 15
Let U=(.
Section 4.3.1: The Classical Algorithms
Exercise 15. [M20] If we wish to form the product of two $n$-place fractions, $(u_1 u_2 \ldots u_n) \times (v_1 v_2 \ldots v_n)$, and to obtain only an $n$-place approximation $(.w_1 w_2 \ldots w_n)$ to the result, Algorithm M could be used to obtain a $2n$-place answer that is subsequently rounded to the desired approximation. But this involves about twice as much work as is necessary for reasonable accuracy, since the products $u_i v_j$ for $i + j > n + 2$ contribute very little to the answer.
Give an estimate of the maximum error that can occur, if these products $u_i v_j$ for $i + j > n + 2$ are not computed during the multiplication, but are assumed to be zero.
Verified: yes
Solve time: 1m19s
Solution
Let
$$ U=(.u_1u_2\cdots u_n)b=\sum{i=1}^{n}u_i b^{-i}, \qquad V=(.v_1v_2\cdots v_n)b=\sum{j=1}^{n}v_j b^{-j}, $$
where $0\le u_i,v_j\le b-1$.
Their exact product is
$$ P=UV=\sum_{i=1}^{n}\sum_{j=1}^{n}u_i v_j, b^{-(i+j)}. $$
To obtain an $n$-place approximation, Algorithm M would ordinarily compute all products $u_i v_j$. The proposed modification omits every term with
$$ i+j>n+2. $$
Let $P'$ denote the product obtained in this way. The error is
$$ E=P-P' =\sum_{i+j>n+2}u_i v_j, b^{-(i+j)}. $$
Since all omitted terms are nonnegative,
$$ 0\le E \le (b-1)^2 \sum_{i+j>n+2} b^{-(i+j)}. $$
Set $s=i+j$. For fixed $s$, the number of pairs $(i,j)$ with
$1\le i,j\le n$ and $i+j=s$ is at most $s-1$. Hence
$$ E \le (b-1)^2 \sum_{s=n+3}^{\infty}(s-1)b^{-s}. $$
Write $r=b^{-1}$. Then
$$ E \le (b-1)^2 \sum_{s=n+3}^{\infty}(s-1)r^s =(b-1)^2 r^{,n+3} \sum_{t=0}^{\infty}(n+2+t)r^t . $$
Using
$$ \sum_{t=0}^{\infty} r^t=\frac1{1-r}, \qquad \sum_{t=0}^{\infty} t r^t=\frac{r}{(1-r)^2}, $$
we obtain
$$ E \le (b-1)^2 r^{,n+3} \left( \frac{n+2}{1-r} +\frac{r}{(1-r)^2} \right). $$
Since $1-r=(b-1)/b$,
$$ E \le b^{-(n+3)} \left( b(b-1)(n+2)+b \right). $$
Therefore
$$ E \le \frac{(b-1)(n+2)+1}{b^{,n+2}}. $$
Hence the omitted products can affect the result by at most
$$ \boxed{ E< \frac{n+3}{b^{,n+1}} }. $$
A sharper estimate is
$$ \boxed{ E\le \frac{(b-1)(n+2)+1}{b^{,n+2}} }. $$
Thus the neglected terms contribute only a quantity of order
$$ O!\left(\frac{n}{b^{,n+2}}\right), $$
which is much smaller than one unit in the $n$th retained digit. Consequently, computing only the products with $i+j\le n+2$ yields essentially the same $n$-place result while requiring only about half of the multiplications.
$$ \boxed{ \text{Maximum error } \le \frac{(b-1)(n+2)+1}{b^{,n+2}} } $$
∎