Euclidean Algorithm

The Euclidean Algorithm is an algorithm that computes $\gcd \{a,b\}$ for non-negative integers $a$ and $b$ in $\mathcal{O}(\log a+\log b)$ time and $\mathcal{O}(\log a+\log b)$ space.

Tip

This problem can also be solved by the Extended Euclidean Algorithm in $\mathcal{O}(\log a+\log b)$ time and $\mathcal{O}(\log a+\log b)$ space.

Algorithm

Lemma

$$\forall a\in \mathbb{N},\forall b\in {\mathbb{Z}}_{+},\gcd \{a,b\}=\gcd \{b,a\mathrm{mod}b\}$$

0. Solve for $\gcd \{b,a\mathrm{mod}b\}$ recursively.

1. Apply the lemma to find $\gcd \{a,b\}$.

This algorithm solves the problem in $\mathcal{O}(\log a+\log b)$ time and $\mathcal{O}(\log a+\log b)$ space.

int euclidean(int a, int b) {
	return y_combinator([&](auto &&self, int a, int b) -> int {
		return b ? self(b, a % b) : a;
	})(a, b);
}

Proof

If $b>0$,

$$\begin{array}{rl}a\ge b& ⟺\lfloor \frac{a}{b}\rfloor b>a\mathrm{mod}b\\ & ⟺a-a\mathrm{mod}b>a\mathrm{mod}b\\ & ⟺a\mathrm{mod}b<\frac{a}{2}\end{array}$$