Euclid's Algorithm Time Complexity

Question

I have a question about the Euclid's Algorithm for finding greatest common divisors.

gcd(p,q) where p> q and q is a n-bit integer.

I'm trying to follow a time complexity analysis on the algorithm (input is n-bits as above)

gcd(p,q)
 if (p == q)
 return q
 if (p < q)
 gcd(q,p)
 while (q != 0)
 temp = p % q
 p = q
 q = temp
 return p

I already understand that the sum of the two numbers, u + v where u and v stand for initial values of p and q , reduces by a factor of at least 1/2.

Now let m be the number of iterations for this algorithm. We want to find the smallest integer m such that (1/2)^m(u + v) <= 1

Here is my question. I get that sum of the two numbers at each iteration is upper-bounded by (1/2)^m(p + q). But I don't really see why the max m is reached when this quantity is <= 1.

The answer is O(n) for n-bits q, but this is where I'm getting stuck.

Please help!!

• hengxin: "the sum of the two numbers, $p + q$ , reduces by a factor of at least 1ドル/2$". Unfortunately, this is not true. For example, $(10, 8) = (8, 2)$.
• gnasher729: However, it is easy to prove that the sum is divided by more than 1.5. Worst case is (p = 2q - eps, q) -> (q, q - eps). Yuval shows the larger number is divided by 1.618 in one step or 1.618^2 in two steps.

Answer 1

Here is the idea of the proof. Throughout, we assume that $p \geq q$.

Let $p^{(t)},q^{(t)}$ be the values of $p,q$ after $t$ iterations, so that $p^{(0)}=p$ and $q^{(0)}=q$.

Let $F_m$ be the $m$th Fibonacci number, which satisfies $F_m = \Theta(\varphi^m),ドル where $\varphi = \frac{1+\sqrt{5}}{2} > 1$. Suppose that $p \leq F_m$. If $q \leq F_{m-1}$ then $p^{(1)} = q \leq F_{m-1}$. If $q \geq F_{m-1}$ then $q^{(1)} = p \bmod q \leq F_{m-2},ドル and so $p^{(2)} = q^{(1)} \leq F_{m-2}$.

This argument shows that if $p \leq F_m$ then after at most (roughly) $m$ steps, the algorithm will terminate (since we cannot have $p \leq F_0 = 0$). Since $F_m$ grows exponentially, it's not hard to check that $p \leq F_{O(n)},ドル where $n$ is now the length of $p$ in bits. Therefore the algorithm terminates in $O(n)$ steps.

If you want a bound depending on $\min(p,q)$ rather than on $\max(p,q),ドル simply notice that $p^{(1)} = q,ドル and run the above analysis on $p^{(1)}$.