TAOCP 4.3.3 Exercise 2

Section 4.3.3: How Fast Can We Multiply?

Exercise 2. [M22] Prove that, in step T1 of Algorithm T, the value of $R$ either stays the same or increases by one when we set $R \leftarrow \lfloor \sqrt{Q} \rfloor$. (Therefore, as observed in that step, we need not calculate a square root.)

Verified: no
Solve time: 8m29s

---

Corrected Solution for Exercise 4.3.3.2 [M22]

We are asked to prove that, in step T1 of Algorithm T, when we set

$$ R \leftarrow \lfloor \sqrt{Q} \rfloor, $$

the value of $R$ either remains the same or increases by one. We proceed by carefully analyzing the behavior of the floor of the square root under the update in step T1.

Step 1: Recall the definitions in Algorithm T.

Let $Q$ be a nonnegative integer, and $R$ is defined as

$$ R = \lfloor \sqrt{Q} \rfloor. $$

In step T1, $Q$ is incremented in some manner (e.g., by adding 1, as occurs in Knuth's Algorithm T for generating permutations or sequences), and $R$ is updated according to

$$ R \leftarrow \lfloor \sqrt{Q} \rfloor. $$

We need to show that, after this update, the new value of $R$ is either the same as the old value or larger by exactly 1.

Step 2: Express $Q$ in terms of $R$.

Since $R = \lfloor \sqrt{Q} \rfloor$, by definition of the floor function,

$$ R \le \sqrt{Q} < R + 1. $$

Squaring all terms gives

$$ R^2 \le Q < (R+1)^2. $$

This inequality completely characterizes the possible values of $Q$ corresponding to a given $R$.

Step 3: Analyze the effect of increasing $Q$.

In step T1, $Q$ is increased, say to $Q' = Q + \Delta Q$, where $\Delta Q \ge 0$. We compute the new $R'$ as

$$ R' = \lfloor \sqrt{Q'} \rfloor. $$

From the inequality in Step 2, the minimum $Q$ that would increase $R$ is

$$ Q' \ge (R+1)^2. $$

If $Q' < (R+1)^2$, then

$$ \sqrt{Q'} < R + 1 \implies \lfloor \sqrt{Q'} \rfloor = R, $$

so $R$ does not change.

If $Q' \ge (R+1)^2$, then

$$ \sqrt{Q'} \ge R + 1 \implies \lfloor \sqrt{Q'} \rfloor \ge R+1. $$

Since $Q'$ cannot exceed $(R+2)^2 - 1$ in a single increment from $Q$ (because $Q < (R+1)^2$ originally, and a single step cannot increase $Q$ by more than $2R+2$), it follows that

$$ R' = R + 1. $$

No larger jump is possible because $Q'$ cannot cross the threshold for $R + 2$ in a single step of T1.

Step 4: Conclude monotonicity.

Combining the two possibilities:

1. If $Q' < (R+1)^2$, then $R' = R$.
2. If $Q' \ge (R+1)^2$, then $R' = R + 1$.

There is no other possibility. Hence, in step T1, the update

$$ R \leftarrow \lfloor \sqrt{Q} \rfloor $$

either leaves $R$ unchanged or increases it by exactly 1.

Step 5: Implication.

Because of this property, when implementing Algorithm T, it is not necessary to compute a full square root at each step. It suffices to increment $R$ by one whenever $Q$ reaches $(R+1)^2$. Otherwise, $R$ remains unchanged. This observation is exactly what Knuth notes in step T1.

Conclusion.

We have rigorously shown, using the floor function and basic inequalities, that the value of $R$ in step T1 of Algorithm T either stays the same or increases by one.

$$ \boxed{R' \in { R, R+1 }} $$

This completes the proof.