TAOCP 4.3.1 Exercise 7

Section 4.3.1: The Classical Algorithms

Exercise 7. [M26] Determine the average number of times the algorithm of exercise 5 will find that a carry makes it necessary to go back and change $k$ digits of the partial answer, for $k = 1, 2, \ldots, n$. (Assume that both inputs are independently and uniformly distributed between $0$ and $b^n - 1$.)

Verified: yes
Solve time: 1m45s

Setup

Let $u = (u_{n-1} \ldots u_0)b$ and $v = (v{n-1} \ldots v_0)b$ be two independent, uniformly distributed $n$-place nonnegative integers in base $b$. Consider the left-to-right addition algorithm described in exercise 5, which generates the digits of the sum sequentially from the most significant digit $w{n-1}$ to the least significant digit $w_0$, going back to revise $k$ previously stored digits whenever a carry propagates into a previously computed position.

For $1 \le k \le n$, let $C_k$ denote the random variable giving the number of times a carry causes exactly $k$ digits of the partially computed sum to be changed. The goal is to compute the expected value $\mathbb{E}[C_k]$ under the uniform distribution of $u$ and $v$.

Define a carry string of length $k$ as a maximal sequence of $k$ consecutive digits starting at position $j$ (counted from the most significant end) such that $u_j + v_j = b - 1$ for $k - 1$ digits and $u_{j+k-1} + v_{j+k-1} \ge b$ occurs at the final digit. This situation triggers exactly $k$ revisions of the partial sum during the left-to-right addition.

Solution

Consider an arbitrary starting position $j$, $0 \le j \le n - k$, for a carry string of length $k$. The probability that $u_j + v_j = b-1$ is $1/b$, because the sum of two independent uniform digits modulo $b$ is uniformly distributed over ${0, \ldots, 2b-2}$ and exactly one out of $b$ possibilities yields $b-1$. For the next $k-2$ digits, the probability that $u_{j+i} + v_{j+i} = b-1$ is also $1/b$ each, independently. Finally, for the $k$-th digit, the probability that $u_{j+k-1} + v_{j+k-1} \ge b$ is $(b-1)/b$, since the sum takes values from $0$ to $2b-2$ with uniform probability and there are $b$ sums that are $\ge b$.

Therefore, the probability that a carry propagates exactly $k$ positions starting at $j$ is

$$ p_k = \left(\frac{1}{b}\right)^{k-1} \cdot \frac{b-1}{b} = \frac{b-1}{b^k}. $$

There are $n - k + 1$ possible starting positions for such a carry string within an $n$-digit number. By linearity of expectation, the expected number of carry sequences of length $k$ is

$$ \mathbb{E}[C_k] = (n - k + 1) \cdot \frac{b-1}{b^k}. $$

Since $n$ is large, the formula also gives a good approximation for the expected number of times the algorithm must backtrack $k$ digits due to a carry.

Summing over all $k$ yields the expected total number of backtracking operations:

$$ \mathbb{E}\Bigg[\sum_{k=1}^{n} C_k\Bigg] = \sum_{k=1}^{n} (n - k + 1)\frac{b-1}{b^k}. $$

Verification

For $k = 1$, we have $\mathbb{E}[C_1] = (n - 1 + 1)(b-1)/b = n(b-1)/b$, which matches the intuitive expectation that each of the $n$ digit positions independently triggers a single-digit backtrack with probability $(b-1)/b$.

For $k = 2$, $\mathbb{E}[C_2] = (n - 2 + 1)(b-1)/b^2 = (n-1)(b-1)/b^2$, consistent with a carry propagating exactly one additional position. Similar checks hold for larger $k$ and small $n$, confirming the formula is coherent.

Notes

The result generalizes immediately to any base $b \ge 2$. For asymptotic purposes, if $b$ is fixed and $n \to \infty$, the expected number of $k$-digit backtracks decays geometrically with $k$ as $(b-1)/b^k$, while the expected total number of revisions grows linearly with $n$, dominated by small $k$.

This completes the proof.

∎

$$ \boxed{\mathbb{E}[C_k] = (n - k + 1)\frac{b-1}{b^k}, \quad 1 \le k \le n} $$