Kizirian

Finding the greatest common divisor in two lines

Euclid's Elements gives a wonderfully simple algorithm for finding the greatest common divisor of two numbers. The algorithm can be expressed in just two lines1.

In [1]:
def euclid_gcd(a: int, b: int) -> int:
    return a if b == 0 else euclid_gcd(b, a % b)

A few tests to show that this implementation is correct

In [2]:
assert euclid_gcd(45, 75) == 15
assert euclid_gcd(75, 45) == 15
assert euclid_gcd(6, 18) == 6
assert euclid_gcd(8, 11) == 1

An even more powerful test is to use Hypothesis to generate inputs and compare them to Python's built-in math.gcd

In [3]:
import math
from hypothesis import given, strategies as st

@given(st.integers(min_value=0), st.integers(min_value=0))
def test_euclid_gcd(a, b):
    assert euclid_gcd(a, b) == math.gcd(a, b)

Performance Metrics

The performance of this simple implementation can be compared to math.gcd by generating a large list of random integer tuples, choosing a tuple at random, and measuring the average execution time to find their greatest common divisor.

In [4]:
from random import choice, randint
rand_tuples = [(randint(0, 10**6), randint(0, 10**6)) for _ in range(10**4)]
In [5]:
%%timeit
euclid_gcd(*choice(rand_tuples))

3.7 µs ± 305 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [6]:
%%timeit
math.gcd(*choice(rand_tuples))

1.41 µs ± 101 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Unsurprisingly, the standard library's implementation is over 2x faster. I haven't dug in to see where it's optimizing, but surely it's at least partly due to being implemented in C.

Other Readings

Excellent intuition and a proof is provided in Algorithms by Dasgupta, Papadimitriou, and Vazirani in Section 1.2.3 Euclid's algorithm for greatest common divisor.

The Wikipedia page on Euclid's algorithm goes into even greater depth and provides interesting history.

Footnotes

  1. This can technically be expressed in one line with
def euclid_gcd(a, b): return a if b == 0 else euclid_gcd(b, a%b)

But this is almost offensively concise.

python math