Greatest common divisor

java

Built-in

1
2
3
4
5
import java.math.BigInteger;

public static long gcd(long a, long b) {
	return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();
}

Recursive

To calculate \( gcd(m, n) \), for given values \( 0 \leq m < n\), Euclid’s algorithm uses the recurrence

\(
\begin{align*}
\begin{cases}
gcd(0, n) = n ; \\
gcd(m, n) = gcd(n \hspace{1mm} mod \hspace{1mm} m, m), \hspace{4mm} for \hspace{1mm} m > 0. \\
\end{cases}
\end{align*}
\)

for example, \( gcd(12, 18) = gcd(6, 12) = gcd(0, 6) = 6 \).

1
2
3
4
5
6
7
8
9
public static long gcd(long a, long b) {
	if (a == 0)
		return b;
	if (b == 0)
		return a;
	if (a > b)
		return gcd(b, a % b);
	return gcd(a, b % a);
}

non mod

1
2
3
4
5
6
7
8
public static long gcd(long a, long b) {
	if (a < b)
		return gcd(b, a);
	if (b == 0)
		return a;
	else
		return gcd(a - b, b);
}

bit operation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static long gcd(long a, long b) {
	if (a < b)
		return gcd(b, a);
	if (b == 0)
		return a;
	else {
		if ((a & 1) == 0) {
			if ((b & 1) == 0)
				return (gcd(a >> 1, b >> 1) << 1);
			else
				return gcd(a >> 1, b);
		} else {
			if ((b & 1) == 0)
				return gcd(a, b >> 1);
			else
				return gcd(b, a - b);
		}
	}
}

One of the best, and most often used, examples to illustrate the nature of algorithms is Euclid’s algorithm, which goes back to the third century b.c.e. It is a procedure described by Euclid to determine the greatest common divisor (gcd) of two positive integers a and b.(Sometimes the greatest common divisor is known as the highest common factor (hcf).) (The Princeton Companion to Mathematics - Part II The Origins of Modern Mathematics - II.4 Algorithms, by Jean-Luc Chabert - 2 Three Historical Examples - 2.1 Euclid’s Algorithm: Iteration)

references