Euclid's Algorithm

euclidsAlgorithm.py

# ------------------------------------------------------------------------
# The following Python code is implemented by Professor Terje Haukaas at
# the University of British Columbia in Vancouver, Canada. It is made
# freely available online at terje.civil.ubc.ca together with notes,
# examples, and additional Python code. Please be cautious when using
# this code; it may contain bugs and comes without any form of warranty.
# Please see the Programming note for how to get started.
#
# The code below implements Euclids' algorithm, perhaps the oldest algorithm
# in current use. Euclid was a Greek mathematician born in 335 BC, the year
# before Alexander the Great started his ten-year war-campaign to conquer
# the Persian Empire. On his journey Alexander visited Egypt and gave the
# architect Deinokrates the task of planning the city of Alexandria at the
# site of the fishing village Rhakotis, a substantial engineering accomplishment.
# Euclid ended up living there for 40 years, where he authored "Elements"
# and thus established the field of geometry. Notice that the word "algorithm"
# stems from the later time of the Persian mathematician Muhammad bin
# Musa al-Khwarizmi (Algoritmi in Latin) who was born in 780 and worked
# at the House of Wisdom in Baghdad.
#
# The task solved by Euclid’s algorithm is finding the largest integer, i.e.,
# greatest common divisor, which divides the two integers without leaving a
# remainder. The algorithm is based on the fact that the greatest common
# divisor will also divide the difference between the two numbers without
# leaving a reminder. Hence, the algorithm of Euclid proceeds by repeatedly
# subtracting the small number from the large number until they are either
# equal, in which case the greatest common divisor is the small number, or
# until the remainder is smaller than the small number. In the latter case,
# the remainder is used as the new small number and the previous small number
# is now the large number. This is repeated until the remainder is zero, at
# which time the small number is the greatest common divisor.
# ------------------------------------------------------------------------

def findGreatestCommonDivisor(a, b):

    # First make sure that a is the largest of the two numbers
    if (a < b):
        c = a
        a = b
        b = c

    # Then loop until convergence
    convergence = False
    while not convergence:

        # Subtract as many multiples of b from a as possible and check the remainder
        remainder = a % b

        # Check for convergence
        if (remainder == 0.0):
            convergence = True
            return b

        else:
            # Let b be the new big number, let the remainder be the new small number, and try again
            a = b
            b = remainder

# Test application for Euclid's algorithm:
a = 25
b = 5
divisor = findGreatestCommonDivisor(a, b)
print("The greatest common divisor of", a, "and", b, "is", divisor)