TAOCP 4.6.3 Exercise 1

Exercise 1. [**] [15] What is the value of $Z$ when Algorithm A terminates?

Verified: yes
Solve time: 3m35s

Corrected Solution for Exercise 4.6.3.1, Part 1

We are asked: What is the value of $Z$ when Algorithm A terminates?

Algorithm A is the standard binary exponentiation algorithm. It maintains the invariant

$$ x^n = Y Z^N $$

throughout the execution of the algorithm (step A2). At termination, step A4 is executed immediately after step A3, and the loop has reduced $N$ to zero. Therefore, at termination we have

$$ N = 0 \quad \text{and hence} \quad x^n = Y Z^0 = Y. $$

Thus the algorithm correctly returns

$$ Y = x^n. $$

Now consider the variable $Z$.

The updates to $Z$ occur in step A3 of Algorithm A:

$Z \gets Z^2$ at each iteration.
If the current least significant bit of $N$ is 1, $Y \gets Y \cdot Z$ (but $Z$ is still squared every iteration).

The exact value of $Z$ at any time depends on the sequence of squarings performed, which in turn depends on the binary expansion of $N$. Specifically:

Let $N = (b_k b_{k-1} \dots b_0)_2$.
Each iteration of the loop processes the least significant bit $b_0$, then shifts $N \gets \lfloor N/2 \rfloor$.
$Z$ is squared each iteration, but whether $Y$ is multiplied by $Z$ depends on $b_0 = 1$ or $0$.

At termination $N = 0$, and the loop exits. There is no simple closed formula for $Z$ in general, because the value of $Z$ depends on the bits of $n$. In particular:

If $n = 0$, the algorithm does not perform any squarings, and $Z = x$.
If $n > 0$, $Z$ has been squared a number of times equal to the number of bits processed, but its final value depends on the last squaring performed in the loop.

Therefore, unlike $Y$, which is guaranteed to equal $x^n$ at termination, $Z$ cannot be expressed as a simple power of $x$ in general. Its exact value is determined dynamically by the loop and the binary representation of $n$.

Conclusion:

At termination,

$$ Y = x^n. $$

The final value of $Z$ is algorithm-dependent and varies with the binary expansion of $n$; there is no general closed form. The previous claim

$$ Z = x^{2^{\lfloor \lg n \rfloor}} $$

is incorrect.

Hence the only guaranteed property at termination is that $Z$ is some intermediate power of $x$ maintained by repeated squaring, but its precise value cannot be written in a simple formula.

\boxed{\text{No simple closed form exists for } Z \text{ at termination. Only } Y = x^n \text{ is guaranteed.}