Loops and the Trivial GCD Algorithm

While loops, intermediate variables, and a factorial function

We now are ready to return to our original computational problem of finding the GCD of two integers a and b. Recall the following algorithm that we presented before for solving this problem.

1. Set a variable d equal to 1. This variable will represent the largest divisor common to a and b that we have found thus far.
2. For every integer n between 1 and the minimum of a and b, we ask: “Is n a divisor of both a and b?” If the answer to this question is “Yes”, then we update the largest identified common divisor d to be equal to the current value of n.
3. After ranging through all these integers, the current value of d must be GCD(a, b).

We call your attention to step 2; how can we perform a task “for every integer” in a range? To show how to implement this idea in pseudocode, we will first solve a simpler problem.

The following algorithm, which we will explain line-by-line in what follows, solves the Factorial Problem. It makes use of a control structure called a while loop.

Factorial(n)
    p ← 1
    i ← 1
    while i ≤ n
        p ← p · i
        i ← i + 1
    return p

Before describing the while loop, let us first focus on lines 2 and 3 of Factorial():

    p ← 1
    i ← 1

The only variables we have worked with thus far are parameters, i.e., variables that are given as input to a function. However, we can also introduce new variables as part of instructions in a function. On the above two lines, we declare two new variables, p and i, both having value 1. We read each of these lines like an equation, in which ← is a variant of the equals symbol; the variable on the left side of ← is assigned the value found on the right side of ←. Once we have declared these two variables, we can use them: p will store the product that we are building, and i will help us keep track of how many numbers we have multiplied thus far.

Now we will discuss the while loop, which in general takes the following hypothetical form:

    while condition X is true
         execute instructions Y
    execute instructions B

The statement while condition X is true is much like if condition X is true, with one small difference. In an if statement, if the condition that we are testing is true, then we enter the if block, and then continue on with the program. In a while loop, if X is true, then after completing the while block and executing the instructions inside the block, we return to test X again. If X is true, then we enter the while block again. We only stop entering the while block and continue on with the rest of the function (i.e., instructions B in the above hypothetical pseudocode) when X stops being true.

In the case of Factorial(), say that our input variable n is equal to 4. We know that p and i both start equal to 1, and so when we reach while i ≤ n, this statement is true and we enter the while block. Within the while block, we encounter the following instructions:

        p ← p · i
        i ← i + 1

These statements may seem perplexing — how can we set a variable equal to itself plus one?

We should clarify how we read a variable assignment with ←. On the right side of ←, we are merely accessing the values of any variables we encounter; we then set the variable on the left side of ← equal to the resulting value on the right side of ←. In this case, when p and i are both 1, we are setting p equal to 1 · 1 = 1, and we are setting i equal to 1 + 1 = 2.

We then check again if i is at most n; it is indeed, and so we enter the while block again, setting p equal to 1 · 2 = 2 and i equal to 2 + 1 = 3. We continue in this fashion, as summarized in the table below, until p = 24 and i = 5; at this point, it is no longer true that i less than or equal to n, and rather than entering the while block, we skip the while block and continue on in the function. All that is left to do is return the value of p, which has the (correct) value 24 since we have multiplied 1 by every number between 1 and 4.

The answer to the preceding question is important, and so we discuss it here. If we neglected to add the line i ← i + 1, then the test i ≤ n would always be true. As a result, we would continue entering the while block over and over again, never hitting a return statement, and the algorithm would never terminate! Such a loop is called an infinite loop and is an error made by beginner and experienced programmers alike.

For loops and another way of writing a factorial function

The case of initializing a variable to 1 and performing some action for every value of this variable up to some upper bound appears so frequently in programming that a special type of loop called a for loop was designed to handle it. An example of a for loop is shown in the modified factorial function below.

AnotherFactorial(n)
    p ← 1
    for every integer i between 1 and n
        p ← p·i
    return p

After initializing p to be equal to 1, the for loop states that we are going to perform an action for every value of i between 1 and n, inclusively. This means that the first time through the for loop, i will be equal to 1, and we will increase i every time we have executed the instructions within the for block, which in this case just consists of setting p equal to the product of the values of p and i. We only stop entering the for block and move on to return p once we have performed the instructions in the for block n times, which means that the steps taken by AnotherFactorial() are the same as those taken by Factorial() from above. However, AnotherFactorial() is a bit easier for us to parse, not to mention that it avoids the possibility of the infinite loop that we demonstrated before because we assume that i increases by 1 each time through the loop.

In general, a for loop takes the following form, where we execute the instructions Y contained within the for block for every value of a variable satisfying some condition X:

    for every value of some variable satisfying condition X
        execute instructions Y

Although for loops make ranging through a given collection of variables convenient, we should note that while loops can be applied to a wider class of functions since they can be applied to test any statement. For example, the following function will only work with a while loop.

PittsburghFebruary()
    while current temperature is below freezing
        daydream about moving to Tampa

Returning to the trivial GCD algorithm

We have now learned enough about pseudocode to return to the GCD Problem and implement the algorithm that we described solving the GCD algorithm. Mathematicians might call this algorithm the trivial algorithm for computing the GCD, since It does not require complicated methods and is perhaps the first method that one would devise to solve this problem.

The pseudocode function below implements the trivial GCD algorithm. This algorithm uses a for loop for convenience, although we could also have used a while loop. Note also that this function allows us to reuse our Min2() function — which you probably thought would never appear again — as a subroutine.

TrivialGCD(a,b)
    d ← 1
    m ← Min2(a,b)
    for every integer p between 1 and m
        if p is a divisor of both a and b
            d ← p
    return d

We can appreciate that TrivialGCD() implements our description of the trivial GCD algorithm. All that remains is to discuss how to test whether one number is a divisor of another.

Given integers n and p, the integer division of n by p is performed by keeping only the integer part of the division and “throwing away” the remainder. For example, if n = 14 and p = 3, then the integer division of n by p is 4 (and the remainder is 2).

If you are interested in checking your solution to the previous two exercises, hang on until we learn how to convert pseudocode into a specific programming language, when we will revisit TrivialGCD(). For now, we are ready to see a much better solution to the GCD problem that was discovered over two millennia ago.