Euclidean Algorithm

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

Algorithm

Lemma

$$\forall a\in \mathbb{Z},\forall b\in \mathbb{Z}\setminus \{0\},\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$$

Applying the lemma yields an algorithm that solves the problem in $\mathcal{O}(\log (a)+\log (b))$ time and $\mathcal{O}(\log (a)+\log (b))$ space.

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

Proof

It is easy to prove that, since the third recursion, $a,b\in \mathbb{N}$ and $a\ge b$.

If $a\in \mathbb{N}$ and $b\in {\mathbb{Z}}^{+}$,

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