0
$\begingroup$

Possible Duplicate:
Runtime of the binary-GCD state machine

Hello I am doing self study from MIT OCW exercises and I could not understand this question. Can anyone explain me,

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

  • Next I dont see where an extra 3 comes from in $3+2log(max(a,b))$

Question: 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.

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

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

states: $\mathbb{N}^3$

start state: $(a,b,1)$, where $a >b>0$

transitions: if $min(x,y) >0$, then $(x,y,e) \rightarrow $

the first possible state according to rules

1- $(1,0,ex)$ if $(x=y)$

2- $(1,0,e)$ if $(y=1)$

3- $(x/2,y/2,2e)$ if $(2|x \ and \ 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)$ if $(otherwise)$

|cite||||||
$\endgroup$