Runtime of Euclidean Algorithm

Question

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: Related question.

Answer 1

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.

• TheEmeritus: 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?
• Yuval Filmus: 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.
• TheEmeritus: 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?
• Yuval Filmus: Sorry, I thought you meant the variant in which you subtract in each step instead of taking the division; I've never seen the variant you describe. Its performance is probably very similar to the more usual one, and I think it will be a nice exercise for you to find out.
• TheEmeritus: Wait, why does $c+d \leq b$?