6
$\begingroup$

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$?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – TheEmeritus Nov 20 '14 at 15:28
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 20 '14 at 15:33
  • $\begingroup$ 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? $\endgroup$ – TheEmeritus Nov 21 '14 at 7:16
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 21 '14 at 15:30
  • $\begingroup$ Wait, why does $c+d \leq b$? $\endgroup$ – TheEmeritus Nov 23 '14 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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