TAOCP — 1.1.1E: Euclid‘s Algorithm

.gitignore

__pycache__

__init__.py

README.md

Book: The Art of Computer Programming, Volume 1: Fundamental Algorithms

Chapter 1

Section 1

Algorithm 1.1E - Euclid's Algorithm

#python #algorithm #implementation #taocp

Algorithm_1_1_1E.py

"""Module to compute GCD(Greatest Common Divisor) of two numbers"""

def gcd(m, n):
    """Function to compute GCD of two numbers"""
    if n > m:
        m, n = n, m

    r = m % n
    if r == 0:
        return n

    return gcd(n, r)

tests.py

from Algorithm_1_1_1E import gcd

assert gcd(51, 17) == 17
assert gcd(119, 544) == 17
assert gcd(12, 8) == 4
assert gcd(8, 8) == 8