TAOCP 7.2.2.2 Exercise 292

Exercise 292. [M21] How large can AGILITY get after repeatedly executing (127)?

Verified: no
Solve time: 2m48s

Solution

Let $A$ denote the current value of AGILITY. Equation (127) updates this 32-bit integer by

$$ A\leftarrow A-(A\gg 13)+ \left(((\operatorname{OVAL}(|l|)-\operatorname{VAL}(|l|))&1)\ll19\right). $$

The last term is either $0$ or $2^{19}$, because the expression inside the shift is a single bit. The largest possible increase therefore occurs whenever the new polarity of $l$ differs from its previous polarity on every execution of (127). In that case the update becomes

$$ A\leftarrow A-\left\lfloor\frac{A}{2^{13}}\right\rfloor+2^{19}. $$

The maximum possible value of $A$ is determined by the balance between the decay term and the repeated additions. The update rule and the interpretation of AGILITY as a 32-bit integer are given in the text following equation (127).

Suppose first that $A<2^{32}-1$. If

$$ A\leq 2^{32}-8193, $$

then

$$ \left\lfloor\frac{A}{8192}\right\rfloor\leq 524286, $$

and hence

$$ A' \geq A-524286+524288=A+2. $$

Thus every value below $2^{32}-8192$ increases by at least $2$ under the most favorable sequence of updates.

For the remaining values,

$$ 2^{32}-8192\leq A\leq 2^{32}-1, $$

we have

$$ \left\lfloor\frac{A}{8192}\right\rfloor=524287, $$

because

$$ \frac{2^{32}-8192}{8192}=524287 $$

and

$$ \frac{2^{32}-1}{8192}<524288. $$

Therefore the update in this range is

$$ A'=A-524287+524288=A+1. $$

In particular, starting from any value below $2^{32}-1$, repeated favorable updates eventually reach $2^{32}-1$. The next application of the update would give

$$ (2^{32}-1)-524287+524288=2^{32}, $$

which is outside the range of a 32-bit unsigned integer. Since AGILITY is stored as a 32-bit integer, the stored value cannot exceed

$$ 2^{32}-1. $$

Therefore the largest possible value reached by repeatedly executing (127) is

$$ \boxed{2^{32}-1=4294967295}. $$

This completes the proof.

∎