TAOCP 7.1.2 Exercise 61
The threshold computation for $t = [p \ge 5]$ is already correct, so the only task is to repair the conditional reduction step so that it actually implements subtraction of $5t$ in a consistent binary...
Section 7.1.2: Boolean Evaluation
Exercise 61. [24] [24] Continuing exercise 60, find a good way to compute $z = (x + y) \bmod 5$, using the three-bit values 000, 001, 010, 011, 100.
Verified: yes
Solve time: 3m58s
The threshold computation for $t = [p \ge 5]$ is already correct, so the only task is to repair the conditional reduction step so that it actually implements subtraction of $5t$ in a consistent binary-adder model.
We restart from the correct intermediate state. We have a 4-bit binary number
$$ p = (p_1 p_2 p_3 p_4)_2, $$
representing an integer in ${0,1,\dots,8}$, and a control bit
$$ t = [p \ge 5] \in {0,1}, $$
correctly given by
$$ t = p_1 \vee \bigl(p_2 \wedge (p_3 \vee p_4)\bigr). $$
The goal is to compute
$$ z = p - 5t $$
using only Boolean chains and full adders.
The previous error arose from treating the vector $(0,t,0,t)$ as if it represented $-5t$, when in fact it represents $+5t$. The correct approach is to explicitly encode $-5$ in 4-bit two’s complement form and then gate that value by $t$.
We first compute the two’s complement representation of $5$ in 4 bits:
$$ 5 = 0101_2. $$
Bitwise negation gives $1010$, and adding $1$ yields
$$ -5 \equiv 1011_2 \pmod{16}. $$
Thus, in 4-bit arithmetic,
$$ -5 = (1,0,1,1) $$
with weights $8,4,2,1$.
To apply this conditionally, we form the masked value
$$ u = t \cdot (-5) = (t, 0, t, t). $$
That is, each bit of $1011$ is ANDed with $t$, so when $t=0$ we add $0000$, and when $t=1$ we add $1011$.
We now define the final computation as a standard 4-bit addition:
$$ z = p + u, $$
where the addition is performed with a ripple-carry full-adder chain.
To verify correctness, we check both cases.
If $t = 0$, then $p \le 4$, so $u = 0000$ and therefore $z = p$, which is correct since $p \bmod 5 = p$ in this range.
If $t = 1$, then $p \in {5,6,7,8}$, and we compute $z = p + 1011_2$. This is exactly
$$ p + 1011_2 \equiv p - 5 \pmod{16}. $$
Because $p \le 8$, subtracting $5$ yields values in ${0,1,2,3}$, so no wraparound ambiguity occurs in 4-bit arithmetic: the result coincides with the ordinary integer difference $p-5$, which is precisely $p \bmod 5$ on this domain.
Thus the construction correctly implements
$$ z = \begin{cases} p, & p \in {0,1,2,3,4},\ p - 5, & p \in {5,6,7,8}, \end{cases} $$
which is exactly $z = (x+y) \bmod 5$.
All operations are realized by standard full-adder circuitry: first compute $p = x+y$, then compute $t$ from the bits of $p$, then form $u$ by bitwise AND with $t$, and finally add $p$ and $u$ in a single ripple-carry adder stage.
This completes a correct Boolean-chain implementation of addition modulo $5$. ∎