The Euclidean algorithm is a well-known algorithm to find Greatest Common Divisor of two numbers. Below is a possible implementation of the Euclidean algorithm in C++:

int gcd(int a, int b) {
    while (b != 0) {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

Time complexity of the $gcd(A, B)$ where $A > B$ has been shown to be $O(\log B)$. Please find a simple proof below:

Proof

Time complexity of function $gcd$ is essentially the time complexity of the while loop inside its body. Let’s say the while loop terminates after $k$ iterations. We are going to prove that $k = O(\log B)$.

Let’s define two sequences $a = \{a_k, a_{k-1}, …, a_0\}$ and $b=\{b_k, b_{k-1}, …, b_0\}$ where $a_{k-i}$ and $b_{k-i}$ the value of variable $a$ and variable $b$ after $i$ iterations $(0 \leq i \leq k)$. Also, let’s define $D = gcd(A, B)$. According to the algorithm, the sequences $a$ and $b$ can be computed using following recurrence relation:

• $a_k = A$
• $b_k = B$
• $\forall i: 1 \leq i \leq k$, we have:
  • $a_{i-1} = b_i$
  • $b_{i-1} = a_i \bmod b_i$
• $a_0 = D$
• $b_0 = 0$

Because $a_{i-1} = b_i$, we can completely remove notation $a$ from the relation by replacing $a_0$ with $b_1$, $a_k$ with $b_{k+1}$, and $a_i$ with $b_{i+1}$:

• $b_k = B$
• $b_{k+1} = A$
• $\forall i: 1 \leq i \leq k, \, b_{i-1} = b_{i+1} \bmod b_i \enspace(1)$
• $b_1 = D$
• $b_0 = 0$

For illustration, the table below shows sequence $b$ where $A = 171$ and $B = 128$.

  i  | b_i  
-----|-----
  7  | 171
  6  | 128
  5  | 48
  4  | 27
  3  | 21
  2  | 6
  1  | 3  <== 3 is the result for gcd(171, 128).
  0  | 0

Define $p_i = b_{i+1} / b_i, \,\forall i : 1 \leq i < k. \enspace (2)$

From $(1)$ and $(2)$, we get: $\, b_{i+1} = b_i * p_i + b_{i-1}$. Put this into the recurrence relation, we get:

• $b_0 = 0$
• $b_1 = D$
• $\forall i: 1 \leq i < k, \,b_{i+1} = b_i \, p_i + b_{i-1}$
• $b_k = B$
• $b_{k+1} = A$

Lemma 1: $\, p_i \geq 1, \, \forall i: 1\leq i < k$.

Proof. According to $(1)$, $\,b_{i-1}$ is the remainder of the division of $b_{i+1}$ by $b_i, \, \forall i: 1 \leq i \leq k$. Therefore, $b_{i-1} < b_{i}, \, \forall i: 1 \leq i \leq k$. Or in other words: $\, b_i < b_{i+1}, \, \forall i: 0 \leq i < k \enspace (3)$. This means: $\, p_i \geq 1, \, \forall i: 1\leq i < k$ because of $(2)$. $\quad \square$

Lemma 2: The sequence $b$ reaches $B$ faster than faster than the Fibonacci sequence.

Proof. Let $f$ be the Fibonacci sequence given by the following recurrence relation: $f_0=0, \enspace f_1=1, \enspace f_{i+1}=f_{i}+f_{i-1}$. We will show that $f_i \leq b_i, \, \forall i: 0 \leq i \leq k \enspace (4)$. This can be proven using mathematical induction:

Base case:
* $(4)$ holds for $i=0$ because $f_0 = b_0 = 0$.
* $(4)$ holds for $i=1 \Leftrightarrow f_1\leq b_1 \Leftrightarrow 1 \leq D \Leftrightarrow 1 \leq gcd(A, B)$, which always holds.

Step case: Given that $(4)$ holds for $i=n-1$ and $i=n$ for some value of $1 \leq n < k$, prove that $(4)$ holds for $i=n+1$, too. That is, given that $f_{n-1} \leq b_{n-1}$ and $f_n \leq b_n$, prove that $f_{n+1} \leq b_{n+1}$.

Indeed, from $f_{n} \leq b_{n}$ and $f_{n-1} \leq b_{n-1}$ (induction hypothesis), and $p_n \geq 1$ (Lemma 1), we infer: $f_{n} + f_{n-1} \leq b_{n} \, p_n + b_{n-1} \Leftrightarrow f_{n+1} \leq b_n$. $\quad \square$

According to Lemma 2, the number of iterations in $gcd(A, B)$ is bounded above by the number of Fibonacci numbers smaller than or equal to $B$. This number is proven to be $1+\lfloor{\log_\phi(\sqrt{5}(N+\frac{1}{2}))}\rfloor$. Hence, time complexity for $gcd(A, B)$ is $O(\log B)$. $\quad \square$