# Runtime of Euclidean Algorithm

Given two $n$-bits numbers $a$ and $b$, I am not sure on how to find the runtime of the euclidean algorithm for finding the $\gcd$ of $a,b$. The problem (for me) in here is that apart from the size of $a$ and $b$, I don't feel like I have any other information that will help me to know what is the runtime of the algorithm. I saw somewhere that the number of rounds is $\log_2 a = n$, but, assuming this is correct, I have no intuition as for why it is such?

My question is for an explanation to how much time it takes to calculate the $gcd$ (as a function of $n$)? Is it linear in $n$?

• – Raphael Nov 20 '14 at 18:53

Let's analyze two consecutive steps of the GCD algorithm: given $a > b$, we compute $c = a \pmod{b}$ (replacing $a$) and $d = b \pmod{c}$ (replacing $b$). The two new numbers $c,d$ we are left with satisfy
$$c+d \leq b \leq \frac{1}{2} (a+b).$$
So the sum of the two numbers decreases by a factor of at least a $1/2$ every two iterations. If $a,b$ are at most $n$-bit long, then at the start of the algorithm, $a+b \leq 2^{n+1}$. After $2(n+1)$ steps, the two remaining numbers have sum at most $1$, so by that time the algorithm must have terminated.
• Thanks! another question I had in my mind is what if I'll change the algorithm so that instead of returning $c=b \mod a$ every time I'll return the minimal between $c$ and $a-c$. It's obvious (by simple number theory arguments) that the algorithm will remain correct. But will it be shorter? Or how can I find it's runtime, when every round I'm taking the minimal one? – TheEmeritus Nov 20 '14 at 15:28
• This algorithm could be very slow. For example, if $a$ is odd and $b = 2$ then the algorithm will converge in roughly $a/2$ steps, which is exponential in the input length. On the other hand, if $a = F_{n+1}$ and $b = F_n$ then the algorithm will converge in roughly $n$ steps, which is linear in the input size. You can probably show that this algorithm always takes at least linearly many steps. – Yuval Filmus Nov 20 '14 at 15:33
• Just noticed we have the opposite "jobs" for $a$ and $b$. So, assuming $a \geq b$, I'll recursively call to find $\gcd (\min{(c,b-c)}, b)$. If $b=2$ and $a$ is odd so $c=1$, thus is most likely the minimum between $c$ and $a-c$, I don't see why it will take $a/2$ steps? – TheEmeritus Nov 21 '14 at 7:16
• Wait, why does $c+d \leq b$? – TheEmeritus Nov 23 '14 at 11:38