TAOCP 4.1 Exercise 16
Let \beta=i-1.
Section 4.1: Positional Number Systems
Exercise 16. [**] [M24] Design an algorithm to add 1 to $(a_n \ldots a_1 a_0)_{i-1}$ in the $i-1$ number system.
Verified: no
Solve time: 5m20s
Let
$$ \beta=i-1. $$
In the $(i-1)$-number system the digits are $0$ and $1$, and every number is represented as
$$ N=\sum_{k\ge0} a_k\beta^k, \qquad a_k\in{0,1}. $$
We first derive the carry rule.
Since
$$ \beta^2=(i-1)^2=-2i, $$
we have
$$ \beta^2+2\beta+2 =(-2i)+2(i-1)+2=0. $$
Hence
$$ 2=-\beta^2-2\beta. $$
Multiplying by $\beta^k$,
$$ 2\beta^k=-\beta^{k+2}-2\beta^{k+1}. $$
Applying the same identity to $2\beta^{k+1}$,
$$ 2\beta^{k+1} =-\beta^{k+3}-2\beta^{k+2}, $$
therefore
$$ 2\beta^k =-\beta^{k+2} +\beta^{k+3} +2\beta^{k+2} =\beta^{k+2}+\beta^{k+3}. $$
Thus
$$ \boxed{2\beta^k=\beta^{k+2}+\beta^{k+3}}. $$
This is the fundamental carry rule.
Algorithm
Suppose
$$ N=(a_n\cdots a_1a_0)_\beta . $$
To compute $N+1$:
A1. Set $a_0\leftarrow a_0+1$.
A2. Scan positions $k=0,1,2,\ldots$.
Whenever $a_k=2$, perform the carry
$$ a_k\leftarrow0,\qquad a_{k+2}\leftarrow a_{k+2}+1,\qquad a_{k+3}\leftarrow a_{k+3}+1. $$
If positions $k+2$ or $k+3$ do not yet exist, create them with initial value $0$.
A3. Continue the scan to the left until every digit is $0$ or $1$.
The resulting digit string is the answer.
Correctness
Each carry step replaces
$$ 2\beta^k $$
by
$$ \beta^{k+2}+\beta^{k+3}, $$
which is valid by the identity proved above. Hence every carry preserves the represented value.
The initial step increases the represented value by exactly $1$. Therefore every subsequent state of the algorithm represents $N+1$.
It remains to show that the process terminates and ends with digits in ${0,1}$.
Termination
Let $L$ be the largest position that is nonzero immediately after Step A1. Since only finitely many digits are present, $L<\infty$.
Consider a carry performed at position $k$.
Before the carry, the contribution of position $k$ to
$$ M=\sum_{j\ge0} j,a_j $$
is $2k$.
After the carry, the contribution of the affected positions is
$$ (k+2)+(k+3)=2k+5. $$
Thus every carry increases $M$ by exactly $5$.
Now observe that every carry also increases the ordinary integer
$$ W=\sum_{j\ge0} a_j $$
by $1$, since one digit $2$ is replaced by two digits $1$.
Let $t$ be the number of carries performed. Then
$$ W\le 1+t, $$
because initially only one digit has been increased.
Furthermore, after $t$ carries all nonzero digits lie in positions at most $L+3t$, since each carry can create digits at most three places farther to the left.
Hence
$$ M \le (1+t)(L+3t). $$
On the other hand, since each carry raises $M$ by $5$,
$$ M=M_0+5t, $$
where $M_0$ is the initial value of $M$.
If infinitely many carries occurred, then for sufficiently large $t$ some position would have to be processed more than once. But after position $k$ has been scanned and reduced from $2$ to $0$, no later carry can affect it, because all future carries originate at positions $>k$ and send carries only to positions still farther left. Therefore each position can be processed at most once.
Since only positions
$$ 0,1,\ldots,L+3t $$
can ever be reached after $t$ carries, and each position is processed at most once, only finitely many carries are possible. Hence the algorithm terminates.
Final normalization
When the scan terminates, no digit equals $2$. Digits are never made negative, and the only values that can occur are $0$, $1$, and temporarily $2$. Therefore every final digit is $0$ or $1$.
Since the final digit string represents the same value as after Step A1, namely $N+1$, the algorithm produces a valid $(i-1)$-representation of $N+1$.
Therefore a correct increment algorithm for the $(i-1)$-system is:
$$ 2\beta^k \longrightarrow \beta^{k+2}+\beta^{k+3}, $$
applied by scanning positions from right to left after adding $1$ to the units digit, until no digit $2$ remains. ∎