GoKawiilIn this section, we will derive a variant of gcd that is ~2x faster than the one in the C++ standard library.
Euclid’s algorithm solves the problem of finding the greatest common divisor (GCD) of two integer numbers $a$ and $b$, which is defined as the largest such number $g$ that divides both $a$ and $b$:
This is true, because if $g = \gcd(a, b)$ divides both $a$ and $b$, it should also divide $(a \bmod b = a - k \cdot b)$, but any larger divisor $d$ of $b$ will not: $d > g$ implies that $d$ couldn’t divide $a$ and thus won’t divide $(a - k \cdot b)$.
The formula above is essentially the algorithm itself: you can simply apply it recursively, and since each time one of the arguments strictly decreases, it will eventually converge to the $b = 0$ case.
The textbook also probably mentioned that the worst possible input to Euclid’s algorithm — the one that maximizes the total number of steps — are consecutive Fibonacci numbers, and since they grow exponentially, the running time of the algorithm is logarithmic in the worst case. This is also true for its average running time if we define it as the expected number of steps for pairs of uniformly distributed integers. The Wikipedia article also has a cryptic derivation of a more precise $0.84 \cdot \ln n$ asymptotic estimate.
You can see bright blue lines at the proportions of the golden ratio
There are many ways you can implement Euclid’s algorithm. The simplest would be just to convert the definition into code:
int gcd ( int a , int b ) { if ( b == 0 ) return a ; else return gcd ( b , a % b ); }
You can rewrite it more compactly like this:
int gcd ( int a , int b ) { return ( b ? gcd ( b , a % b ) : a ); }
... continue reading