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

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Nov 20, 2014 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
    Commented Nov 20, 2014 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
    Commented Nov 21, 2014 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
    Commented Nov 21, 2014 at 15:30
  • $\begingroup$ Wait, why does $c+d \leq b$? $\endgroup$
    – TheEmeritus
    Commented Nov 23, 2014 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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