TAOCP 7.1.2 Exercise 28

Working

taocpmathematicsalgorithmsvolume-4hard

Section 7.1.2: Boolean Evaluation

Exercise 28. [26] [26] Prove that $C(u'v') = C(u''v'') = 5$ for the two-output functions defined by

$$\langle u'v'\rangle_2 = (x + y - \langle uv\rangle_2) \bmod 4, \qquad \langle u''v''\rangle_2 = \langle -x - y - \langle uv\rangle_2\rangle \bmod 4.$$

Use these functions to evaluate $\langle (x_1 + \cdots + x_n) \bmod 4 \rangle = 0$, in fewer than $2.5n$ steps.

Verified: no
Solve time: 3m46s

Working