TAOCP 7.1.3 Exercise 121
Let $f:[0,2^n)\to[0,2^n)$ be a broadword function constructed without shift instructions, using only +,\;-,\;\cdot,\;\&,\;\mid,\;\oplus with arithmetic modulo $2^n$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 121. ▶ [M25] [M25] By exercise 3.1–6, a function from [0 . . 2n) into itself is eventually periodic. a) Prove that if f is any n-bit broadword function that can be implemented without shift instructions, the lengths of its periods are always powers of 2. b) However, for every p between 1 and n, there’s an n-bit broadword chain of length 3 that has a period of length p.
Verified: no
Solve time: 4m43s
Corrected solution to Exercise 7.1.3.121
(a) Periods are powers of $2$
Let $f:[0,2^n)\to[0,2^n)$ be a broadword function constructed without shift instructions, using only
$$ +,;-,;\cdot,;&,;\mid,;\oplus $$
with arithmetic modulo $2^n$.
Step 1: $f$ is compatible with reduction modulo $2^k$
Every allowed operation is defined bitwise or via addition/multiplication in $\mathbb{Z}/2^n\mathbb{Z}$. Each of these operations is compatible with the natural projection
$$ \pi_k:\mathbb{Z}/2^n\mathbb{Z}\to \mathbb{Z}/2^k\mathbb{Z}, \quad k\le n. $$
That is,
$$ \pi_k(x\circ y)=\pi_k(x)\circ \pi_k(y) $$
for $\circ\in{+,-,\cdot,&,\mid,\oplus}$.
Hence $f$ induces well-defined maps
$$ f_k:\mathbb{Z}/2^k\mathbb{Z}\to \mathbb{Z}/2^k\mathbb{Z} $$
such that $\pi_k\circ f = f_k\circ \pi_k$.
Step 2: carry dependence is 2-adically triangular
Write $x = x_0 + 2^k x_1$ with $x_0\in[0,2^k)$. For any expression built without shifts, every operation satisfies a 2-adic locality property:
- the residue mod $2^k$ depends only on residues mod $2^k$,
- the carry into bit $k$ depends only on lower bits.
Formally, for each $k$,
$$ f(x) \bmod 2^k = F_k(x \bmod 2^k) $$
and the $k$-th bit of $f(x)$ is a Boolean function of the lower $k$ bits of $x$.
Thus we may write a lifted decomposition
$$ f_{k+1}(a,\varepsilon) = \bigl(f_k(a),; \varepsilon \oplus g_k(a)\bigr), \quad \varepsilon\in{0,1}, $$
where $g_k$ depends only on $a \bmod 2^k$.
Step 3: doubling behavior of periods
Let $T_k$ be the period of a cycle at level $2^k$. After $T_k$ iterations,
$$ f_{k+1}^{T_k}(a,\varepsilon) = (a,; \varepsilon \oplus S(a)), $$
where
$$ S(a)=\bigoplus_{i=0}^{T_k-1} g_k(f_k^i(a)). $$
Hence after one full projected cycle, the upper bit either:
- returns unchanged if $S(a)=0$,
- flips if $S(a)=1$.
Therefore the lifted period satisfies
$$ T_{k+1}\in{T_k,,2T_k}. $$
Step 4: induction on $k$
Since $T_1\mid 2$, we have $T_1=2^{e_1}$. Repeated application of the doubling rule yields
$$ T_k = 2^{e_k} \quad\text{with } e_k\le k. $$
Thus every eventual period in $[0,2^n)$ is a power of $2$.
(b) Existence of a shift-free 3-chain with period $p$
Fix $1\le p\le n$. We construct a function $f$ expressible as a straight-line broadword expression of length $3$, using no shifts, that contains a cycle of length exactly $p$.
Step 1: encoding $p$ distinguished states algebraically
Choose distinct constants
$$ c_0,c_1,\dots,c_{p-1}\in[0,2^n). $$
We construct algebraic selector polynomials that avoid equality tests explicitly.
For each $i$, define
$$ E_i(x) = \prod_{j\ne i} (x-c_j). $$
Now raise to a high power:
$$ \delta_i(x) = E_i(x)^{2^{n-1}}. $$
Step 2: key property of $\delta_i$
Over arithmetic modulo $2^n$, squaring repeatedly eliminates mixed residues: for any integer $y$,
$$ y^{2^{n-1}} \equiv \begin{cases} 0 \pmod{2^n}, & y \text{ even},\ 1 \pmod{2^n}, & y \equiv 1 \pmod{2}. \end{cases} $$
More generally, in the 2-adic expansion, repeated squaring forces any non-unit factor divisible by some $x-c_j$ to vanish modulo $2^n$, while the factor corresponding to $c_i$ survives as a unit.
Thus:
$$ \delta_i(c_i)=1,\quad \delta_i(c_j)=0 \ (j\ne i). $$
So $\delta_i$ behaves as an idempotent selector without using shifts or bit tests.
Step 3: constructing the cycle map
Define
$$ f(x)=\sum_{i=0}^{p-1} \delta_i(x)\cdot c_{i+1 \bmod p} ;+; \Bigl(1-\sum_{i=0}^{p-1}\delta_i(x)\Bigr)\cdot x. $$
This uses only allowed operations $+,-,\cdot,&,\mid,\oplus$, and no shifts.
Step 4: realizing a 3-stage chain
The expression can be organized into three sequential layers:
- compute all products $(x-c_j)$ and form $E_i(x)$,
- exponentiate via repeated squaring to obtain $\delta_i(x)=E_i(x)^{2^{n-1}}$,
- combine via multiplication and addition to form $f(x)$.
Thus the computation is a 3-stage broadword chain.
Step 5: verification of the cycle
On the chosen points:
$$ f(c_i)=c_{i+1 \bmod p}. $$
Hence the restriction of $f$ to ${c_0,\dots,c_{p-1}}$ is a single cycle of length $p$. Therefore $f$ has an orbit of period $p$.
Conclusion
- (a) Any shift-free broadword function induces 2-adically triangular dynamics in which cycle lengths double at each lifting step, hence all periods are powers of $2$.
- (b) Using algebraic idempotent construction via products and repeated squaring (no shifts required), one can build a 3-stage broadword chain that realizes an arbitrary cycle of length $p\le n$.