TAOCP 7.1.4 Exercise 20

Exercise 20. [15] [15] Devise a fast way to compute the Thue–Morse weights (15) for 1 ≤j ≤n.

Verified: yes
Solve time: 1m53s

Solution

Let $t(m)$ denote the parity of the binary digit sum of $m$, so that $t(m)=0$ when $m$ has an even number of 1s in binary representation and $t(m)=1$ otherwise. The Thue–Morse weight is given in (15) as

$$ w_j = (-1)^{t(j-1)}, \qquad 1 \le j \le n. $$

Equivalently, $w_j = 1$ when $t(j-1)=0$ and $w_j=-1$ when $t(j-1)=1$.

Let $a(m)=(-1)^{t(m)}$ for $m \ge 0$. Then $w_j=a(j-1)$. The binary structure of $m$ splits according to its least significant bit. If $m=2k$, the binary representation of $2k$ is that of $k$ shifted left by one position, so $t(2k)=t(k)$ and therefore

$$ a(2k)=(-1)^{t(2k)} = (-1)^{t(k)} = a(k). $$

If $m=2k+1$, then the binary representation of $2k+1$ has one additional $1$ bit compared to $2k$, so $t(2k+1)=t(k)+1$ and

$$ a(2k+1)=(-1)^{t(2k+1)} = (-1)^{t(k)+1} = -a(k). $$

Thus

$$ a(0)=1,\qquad a(2k)=a(k),\qquad a(2k+1)=-a(k). $$

To compute $w_1,\dots,w_n$, it suffices to compute $a(0),\dots,a(n-1)$ using this recurrence. The dependency graph is acyclic under the natural order of integers, so filling values in increasing order yields all required predecessors already computed.

For each integer $m \ge 1$, writing $m=2k$ or $m=2k+1$ expresses $a(m)$ directly in terms of $a(k)$, and $k < m$, so each value is determined after its parent is available. The computation performs exactly one assignment per $m$ after initialization of $a(0)$.

The resulting procedure is:

$$ a(0)\leftarrow 1, $$

$$ \text{for } m \leftarrow 1 \text{ to } n-1 \text{ do} \quad \begin{cases} a(m)\leftarrow a(m/2) & \text{if } m \text{ is even},\ a(m)\leftarrow -a(\lfloor m/2 \rfloor) & \text{if } m \text{ is odd}. \end{cases} $$

Finally set $w_j \leftarrow a(j-1)$ for $1 \le j \le n$.

Each integer $m$ requires exactly one lookup and one sign change in the odd case or one lookup in the even case, so the total number of basic updates is linear in $n$. No method can compute all $w_j$ without producing $n$ output values, so any correct computation requires at least $n$ assignments to store the results, matching the order of this construction.

Hence the Thue–Morse weights for $1 \le j \le n$ are obtained in linear time by the binary recurrence.

$$ \boxed{w_j = (-1)^{t(j-1)},\ \text{computed via } a(0)=1,\ a(2k)=a(k),\ a(2k+1)=-a(k)} $$