This problem is adapted from chapter 6 of "Mathematics for Computer Science" (Lehman, Leighton, Meyers, 2018).
Problem
Consider the following fast exponentation algorithm.
Given inputs $a\in\mathbb{R},b\in\mathbb{N}$, initialize registers $x,y,z$ to $a,1,b$ respectively, and repeat the following sequence of steps until termination:
if $z=0$ return $y$ and terminate
$r:=\text{remainder}(z,2)$
$z:=\text{quotient}(z,2)$
if $r=1$, then $y:=xy$
$x:=x^2$
The behavior of this algorithm can be modelled with a state machine:
states := $\mathbb{R}\times\mathbb{R}\times\mathbb{N}$,
start state := $(a,1,b)$,
transitions are defined by the following rule:
$(x,y,z)\rightarrow \begin{cases}
(x^2,y,\text{quotient}(z,2)) & \text{if }z\text{ is nonzero and even,} \\
(x^2,xy,\text{quotient}(z,2)) & \text{if }z\text{ is nonzero and odd.}
\end{cases}$
Prove that the fast exponentiation state machine will halt after $\lceil \log_2n \rceil+1$ transitions starting from any state where the value of $z$ is $n\in \mathbb{Z}^+$.
Solution attempt
Proof by strong induction.
Induction hypothesis: $P(n)$ := for any state $s=(x,y,z)$ where $z = n\in \mathbb{Z}^+$, the fast exponentiation state machine will stop after $\lceil \log_2n \rceil+1$ transitions.
Base case: $P(1)$ is true, because, starting from any state where $z = 1$:
-
the first transition will move to a state where $z = \text{quotient}(z, 2) = 0$
-
since $z$ is now $0$, there are no further transitions.
Therefore, there is only $1 = \lceil \log_2(1) \rceil+1$ transition.
Inductive step:
Assume that, for some $n \geq 1$, $P(k)$ is true for all $k \leq n$.
We want to show that $P(n+1)$ is true; that is, we want to show that, for any state $s=(x,y,z)$ where $z = n+1$, the fast exponentiation state machine will stop after $\lceil \log_2(n+1) \rceil+1$ transitions.
Let $s$ be a state of the fast exponentiation state machine where $z = n + 1$.
Let $t$ be a state such that there is a transition from $s$ to $t$.
Applying such transition, the state $t$ will have
$z_t = \begin{cases}
(n+1)/2 & \text{if }n+1\text{ is even,} \\
(n/2) & \text{if }n+1\text{ is odd.}
\end{cases}$
Since both possible values of $z_t$ ($(n+1)/2$ and $n/2$) are smaller than $n + 1$, the induction hypothesis can be applied for state $t$.
Let $T$ denote the number of transitions starting from $t$ after which the state machine will halt. Then, the number of transitions starting from $s$ will be 1 + $T$.
To find the value of $T$, there are two cases:
-
$n+1$ is even:
$z_t = (n+1)/2$, so, by the induction hypothesis $P((n+1)/2)$, the state machine starting from state $t$ will stop after $\lceil \log_2((n+1)/2) \rceil + 1$ transitions.
$T=\lceil \log_2((n+1)/2) \rceil + 1 = \lceil \log_2(n+1) – 1 \rceil + 1 = \lceil \log_2(n+1) \rceil$
-
$n+1$ is odd:
$z_t = n/2$, so, by the induction hypothesis $P(n/2)$, the state machine starting from state $t$ will stop after $\lceil \log_2(n/2) \rceil+1$ transitions.
$T=\lceil \log_2(n/2) \rceil+1 = \lceil \log_2n – 1 \rceil+1 = \lceil \log_2n \rceil$
Since $\lceil \log_2(n+1) \rceil \gt \lceil log_2n \rceil$, then, in both cases above, $T$ is at most $\lceil \log_2(n+1) \rceil$.
Therefore, the number of steps starting from state $s$ is at most $1 + \lceil \log_2(n+1) \rceil$.
This proves $P(n+1)$.
Therefore, by strong induction, $P(n)$ is true for all $n \geq 1$.
Can anyone please verify this solution attempt?
Best Answer
If you look closely, the parts of the algorithm that are relevant to discuss the number of steps are
Repeat the following sequence of steps until termination:
But you can notice that
$$\text{quotient}(\text{quotient}(z_0,2),2)=\text{quotient}(z_0,2^2)$$ and more generally, by induction, the effect of $k$ iterations is
$$z:=\text{quotient}(z_0,2^k).$$
So $z$ is nonzero as long as
$$2^k\le z_0,$$ and becomes zero when
$$2^{k-1}\le z_0<2^k$$ or
$$k-1\le\log_2z_0<k.$$