Published: 22 June 2024 | Updated: 28 June 2024
Probably the most famous algorithm in number theory and algebra is the Euclidean algorithm. It is named after the ancient Greek mathematician Euclid. The algorithm is used to compute the greatest common divisor ($\mathrm{gcd}$) of two integers.
I first introduce the $\mathrm{gcd}$ formally. For an integer $a\in\mathbb{Z}$ let $D_a = \lbrace n\in\mathbb{N}\colon n\mid a\rbrace$ denote the set of all positive integers that divide $a$, i.e. are factors of $a$. The $\mathrm{gcd}$ can in fact be interpreted as a function of two integers given by
$$ \begin{aligned} &\mathrm{gcd}\colon\mathbb{Z}\times\mathbb{Z}\setminus\lbrace(0,0)\rbrace \to \mathbb{N},\\ &(a,b)\mapsto \max\lbrace n\in D_a\cap D_b \rbrace. \end{aligned} $$
The $\mathrm{gcd}$ has got some useful properties:
1, 2 and 3 are clear, for 4 I’ll give a proof.
Let $c=\mathrm{gcd}(a,b)$ and $d$ a common divisor of $a-kb$ and $b$ for $k\in\mathbb{Z}$. Obviously, $c$ divides $a-kb$, which means that $c$ is also a common divisor of $a-kb$ and $b$. What remains to show is that $d\leq c$. We know that $(a-kb)/d$ and $kb/d$ are both integers and so is their sum
$$ \begin{align} \frac{a-kb}{d} + \frac{kb}{d} = \frac{a}{d}. \end{align} $$
From this, we derive that $d$ divides $a$. In particular, $d$ is a common divisor of $a$ and $b$ and, since $c$ is the greatest common divisor of these numbers, $d$ must be less or equal to $c$.
Points 1, 2, and 3 can be used for a kind of preprocessing. We sort out those cases which are either not of interest to us (negative numbers) or very simple ($a$ or $b$ zero). In Java, this can be realized as follows:
int euclideanAlg(int a, int b){
// preprocessing
a = Math.abs(a);
b = Math.abs(b);
if (a==0 && b==0) {
System.err.println("Unbounded problem!");
return -1;
}
if (a==0) {
return b;
}
if(b==0) {
return a;
}
// call of the actual algorithm
return executeEuclideanAlg(a, b)
}
The actual algorithm will be implemented in the method executeEuclideanAlg, which now receives two non-negative integers as arguments. For this we can use the fourth of the above mentioned properties of the $\mathrm{gcd}$: $\mathrm{gcd}(a,b)=\mathrm{gcd}(a-kb,b)$ for all $k\in\mathbb{Z}$.
What does this property mean for us? Put simply, iteratively applied (using symmetry), it reduces the complexity of the computation by replacing the numbers with smaller ones. On this observation will we build up our implementation. We face the following questions:
The answer to the second is simple. It is quite natural to use recursion, until a tuple $(a_m, b_m)$ of two integers is found where we directly return their greatest common divisor. This is the case, when $a_m$ divides $b_m$ or vice versa.
Since our aim are as few recursion calls as possible, we need to decrease the initial integers $a$ and $b$ as fast as possible, but avoid negative numbers at the same time. This can be achieved if we decrease in each iteration the bigger number by the biggest possible factor, such that the resulting number is still non-negative.
In other words, in each iteration we need to find the greatest $k\in\mathbb{N}$, such that
$$ \begin{align}\tag{1}\label{eq:1} \max\lbrace a,b\rbrace - k \min\lbrace a,b\rbrace \geq 0. \end{align} $$
This is equivalent to $k\leq\max\lbrace a,b\rbrace / \min\lbrace a,b\rbrace$. Since $k$ must be an integer, we round it off and get that
$$ \begin{align} \hat{k}=\bigg\lfloor \frac{\max\lbrace a,b\rbrace}{\min\lbrace a,b\rbrace} \bigg\rfloor \end{align} $$
is the greatest non-negative integer for which \eqref{eq:1} holds. More precisely, we have $$ \begin{align}\tag{2}\label{eq:2} \max\lbrace a,b\rbrace = \hat{k}\cdot\min\lbrace a,b\rbrace + r, \end{align} $$ where $r$ is the remainder of the division of the maximum of $a$ and $b$ by the minimum.
We can now implement the Euclidean Algorithm:
int executeEuclideanAlg(int a, int b) {
int max = a > b ? a : b;
int min = max == a ? b : a;
// exit condition for recursion
// min divides max
if(max % min == 0){
return min;
}
// recursion call
// decrease bigger integer, use k = Math.floorDiv(max, min)
return executeEuclideanAlg(max-Math.floorDiv(max, min) * min,min);
}
That’s a good, basic implementation.
A first step of enhancement is to get rid of the recursion and use a loop instead. With a while-loop, the method now looks as shown below. Notice, that temp is always less than the current min.
int executeEuclideanAlg(int a, int b) {
int max = a > b ? a : b;
int min = max == a ? b : a;
int temp;
while(max % min > 0) {
temp = max-Math.floorDiv(max, min) * min;
max = min
min = temp
}
// min divides max
return min;
}
It’s not that easy to calculate the runtime complexity of the algorithm. It´s $O(\log(\min\lbrace a,b\rbrace))$. I won’t elaborate on this. There are plenty of sources where you’ll find an explanation.
A logarithmic time is really good; actually a bit astonishing for such a powerful algorithm. Without prior knowledge about $a$ and $b$ this cannot be improved to a linear runtime.
Still, there is one last step to practically make our algorithm faster. There are two divisions carried out in each iteration (one in the modulo operation and one in the floorDiv method). Divisions, however, have far more computational costs than, for example, multiplications or additions.
Let’s analyse the second division more thoroughly by rewriting the term. In view of \eqref{eq:2} we have
$$
\begin{align}
&\text{max} - \bigg\lfloor\frac{\text{max}}{\text{min}}\bigg\rfloor \text{min} \\ =\ &\text{max} - \frac{\text{max}-r}{\text{min}}\text{min} = r.
\end{align}
$$
And this $r$ is nothing else but max % min. Thus, we can save on one division per iteration. Using this, we obtain the final, refined version of the algorithm:
int executeEuclideanAlg(int a, int b) {
int max = a > b ? a : b;
int min = max == a ? b : a;
// remainder
int r = max % min;
while(r > 0) {
max = min;
min = r;
r = max % min;
}
// min divides max
return min;
}
All in all, the result is an easy to read, fast implementation of the Euclidean algorithm that, due to the preprocessing, doesn’t suffer from integer overflow, and thus computes the greatest common divisor of two arbitrary integers correctly.