Termination of a Fast Exponentiation problem

Question

Here's the problem I am stuck on. There exists a fast exponentiation program like the following:

---

Given inputs a in the set of all Real numbers, b in the set of Natural numbers, 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 := remainder(z, 2)
• z := quotient(z, 2)
• if r = 1, then y:= xy
• x:= x^2

---

So, the start state of this state machine is a, 1, b and its transitions are (x, y, z) --> {(x^2, y, quotient(z,2), (x^2, xy, quotient(z,2)}

Now, I need to prove that this state machine will terminate after [log2(n)] + 1 transitions starting from any state where z is n such that n is a positive integer.

The track I'm on is that I assume that for all z >=1, the number of transitions = log2(z) + 1, then prove that by adding one more transition, the first transition where z = 0, we can prove that it halts there. Right now I have no idea how to prove this, or if the track I'm on is right at all.

Edit: the hint on the problem is "prove by strong induction"

Answer 1

As $z$ only depends on $z$ (and its initial state $b$) you should not care about any other variable in order to see if the problem ends.

It does, you can see that $z_n\le\frac12z_{n-1}$ (for $z_n$ the value of $z$ after the $n^{\text{th}}$ iteration) and it is always a non-negative integer, so $z_n\le2^{-n}z_0$ with $z_0=b$. So $\log_2z_n\le\log_2b-n$, so when $n=\lfloor\log_2b\rfloor$ we know that $\log_2z_n\le\log_2b-\lfloor\log_2b\rfloor<1$ with $z_n\in\{0,1\}$.

Now, there is $k$ such as $2^k\le b<2^{k+1}$. So we have: $$ 2^k\le z_0<2^{k+1} \\ 2^{k-1}\le z_1<2^{k} \\ 2^{k-2}\le z_2<2^{k-1} \\ \vdots\\ 2^{k-k}\le z_k<2^{k-k+1} $$ For this: $1\leq z_k<2$, and finally $z_{k+1}<1$.

So at step $k+1$ the problem ends. And $k=\lfloor\log_2b\rfloor$, so the number of iterations is $\lfloor\log_2b\rfloor+1$.

---

Note:

What needs strong induction is to prove that, at the end, $y=a^b$.

Answer 2

Hint: Clearly you need to concentrate on the lines

• if z = 0 return y and terminate
• z := quotient(z, 2)

because they are the only ones that affect the flow. For an inductive proof, start with the base case: how many times does the loop execute if $z=1$? Does that equal $\lceil \log_2 z \rceil +1$?

Now assume the expression is true for all numbers $1$ through $k$, that when called with $z=m$ the loop executes $\lceil \log_2 m \rceil +1$ times. When called with $z=k+1$, you need to show that it executes $\lceil \log_2 (k+1) \rceil +1$ times. As $\lceil \log_2 (k+1) \rceil = \lceil \log_2 (\frac {k+1}2) \rceil+1$...