Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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))$.

share|improve this question
2  
Welcome! You question is not self-contained. Which machine are you talking about? Or are 1- to 7- supposed to define it? I have trouble following your language. Maybe it would help if you stated the exercise problem first, and then your problem with it. –  Raphael Oct 31 '12 at 16:16
    
If you're having trouble with your account, see the help. You'd have an easier time with an OpenID (Facebook, Google, etc., or Stack Exchange's own), see the help for adding one. –  Gilles Oct 31 '12 at 18:24
1  
The problem doesn't ask you to prove that it halves $(max(a,b))$ every two transitions. It asks you to prove that it runs in $3 + 2 \log (\max(a,b))$ transitions total. There's a difference. For example, you might try showing that it always quarters $(\max(a,b))$ in four transistions. –  Peter Shor Oct 31 '12 at 18:35
    
I tried to format your question in a readable and comprehensible form. Please check I did not change its meaning. –  Raphael Oct 31 '12 at 23:36
    
I believe this algorithm is attributed to Roland Silver and analyzed in detail in Knuth's TACOP, Vol. 2, Seminumerical Algorithms. You may want to consult this tome to get ideas about tackling the problem you are trying to solve. –  Dilip Sarwate Nov 1 '12 at 12:07
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.