Runtime of the binary-GCD state machine

Question

I am doing self study from MIT OCW exercises and I could not understand this question.

The following rules define the binary-GCD state machine working on states in $\mathbb{N}^3$ with start state $(a,b,1)$ for $a>b>0$. If multiple rules apply, smaller numbers have precedence.

Provided $\min(x,y) >0$, then $(x,y,e) \to $

1. $(1,0,ex)$ if $x=y$
2. $(1,0,e)$ if $y=1$
3. $(x/2,y/2,2e)$ if $2|x \land 2|y$
4. $(y,x,e)$ if $y>x$
5. $(x,y/2,e)$ if $2|y$
6. $(x/2,y,e)$ if $2|x$
7. $(x-y,y,e)$ otherwise

The binary-GCD state machine computes the GCD of $a$ and $b$ using only division by $2$ and subtraction, which makes it run very efficiently on hardware that uses binary representation of numbers. In practice, it runs more quickly than the Euclidean algorithm state machine.

Each execution of a command (one of rules 1-7 according to algorithm) is a transition and the current state $(x,y,e)$ is stored in registers $A,B,E$. At first the values in the registers $a,b,1$

Here is the question I am having trouble with:

Prove that the machine reaches a final state in at most $3+2\log(\max(a,b))$ transitions.

Hint: Strong induction on $\max(a,b)$

• First, why does this state machine assume it halves the $\max(a,b)$ at every two transitions beacuse we can apply rule 4 and 7 and one extra rule to halve the $\max(a,b)$, which is more than two transitions/steps. I know it is not a common case but a case is a case unless proved.

• Next I don't see where an extra 3 comes from in $3+2\log(\max(a,b))$.

Answer 1

Unless I've done this example wrong, this question is asking you to prove something that isn't true. Consider $(x,y) = (381,192) = (3\cdot 127,3\cdot 64)$. What happens when you run the algorithm?

$(3\cdot127,3\cdot 64,1) \rightarrow (3\cdot127,3\cdot 32,1) \rightarrow \ldots \rightarrow (3\cdot 127,3,1)$
$ (3\cdot 127,3,1) \rightarrow (3\cdot 126,3,1) \rightarrow (3\cdot 63,3,1) \rightarrow \ldots \rightarrow (3,3,1) $
$ (3,3,1) \rightarrow (1,0,3) $

So starting with $( 3\cdot (2^k -1), 3 \cdot 2^{k-1}, 1)$, the first set of steps applies the 5th rule $k-1$ times, resulting in $(3 \cdot (2^k-1), 3, 1)$. We then alternately apply the 7th rule and the 6th rule. Each time we do this, we go from $(3\cdot (2^j-1),3,1)$ to $(3\cdot (2^{j-1}-1),3,1)$, until we reach $(3\cdot(2^1-1),3,1)$. This takes $2(k-1)$ transitions. Finally, we apply the 1st rule once, for a total of $3k-2$ transitions. But the original value has $\log_2 \max(x,y) \approx {k}$, so we needed $3 \log_2 \max(x,y) - C$ transitions total for some constant $C$.

It's certainly true, and not hard to prove, that the algorithm runs in $O(\log \max(x,y))$. But the question has the constant wrong.