1
$\begingroup$

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!!

$\endgroup$
  • $\begingroup$ "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)$. $\endgroup$ – hengxin Mar 29 '17 at 3:38
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Mar 29 '17 at 19:53
2
$\begingroup$

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)}$.

$\endgroup$

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.