Implementing GCD Algorithms in Go

Learning objectives

We are now ready to return to the two algorithms for finding the GCD of two integers that we presented in the main text on the level of pseudocode. In TrivialGCD(), we consider every possible divisor p between 1 and the minimum of the two input integers a and b, and take the largest common divisor.

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 then introduced EuclidGCD(), which iteratively subtracts the smaller of the two integers from the larger until they are both equal.

EuclidGCD(a, b)
    while a ≠ b
        if a > b
            a ← a − b
        else
            b ← b − a
    return a 

We claimed that EuclidGCD() is a more efficient algorithm than TrivialGCD(). In this lesson, we will implement these two algorithms in Go and then time them to test our hypothesis.

Set up

Create a new folder called gcd in your go/src directory, and then create a new file within the go/src/gcd folder called main.go, which we will edit in this lesson.

In main.go, add the following starter code.

package main

import (
    "fmt"
)

func main() {
    fmt.Println("Implementing two GCD algorithms.")
}

Code along video

Beneath the video, we provide a detailed summary of the topics and code covered in the code along.

At the bottom of this page, you will have the opportunity to validate your work via auto-graded assessments that evaluate the functions covered in the code along.

Although we strongly suggest completing the code along on your own, you can find completed code from the code along in our course code repository.

Code along summary

Implementing the trivial GCD algorithm

We start with TrivialGCD(), reproduced below.

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

Our introductory work has equipped us with most of what we need to know to implement this function, since we have discussed for loops and if statements, and we have already implemented a Min2() function that TrivialGCD() uses as a subroutine. We reproduce the Go implementation of Min2() below; make sure that it is present in main.go so that it will be visible to our implementation of TrivialGCD().

func Min2(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

We are nearly ready to implement TrivialGCD(), but we must first determine how to implement the line that tests whether p is a divisor of both input integers,

        if p is a divisor of both a and b

First, note that we can rewrite TrivialGCD() using two nested if statements instead of a single statement, as follows. This change allows us to focus solely on determining whether one integer is a divisor of another.

TrivialGCD(a,b)
    d ← 1
    m ← Min2(a,b)
    for every integer p between 1 and m
        if p is a divisor of a
            if p is a divisor of b
                //if we make it here, we know that p is a divisor of both a and b
                d ← p
    return d

From the previous code along, we know how to test when p is a divisor of a: it is when a % p, the remainder of the division of a by p, is equal to zero.

func TrivialGCD(a, b int) int {
    d := 1
    m := Min2(a, b)
    for p := 1; p <= m; p++ {
        if a % p == 0 {
            if b % p == 0 {
                //if we make it here, we know that p is a divisor of both a and b
                d = p
            }
        }
    }
    return d
}

Let’s call our function on a couple of integers. Type the following code into func main(), and then compile and run your code. It should print the correct value of 21.

func main() {
    x := 63
    y := 42
    fmt.Println(TrivialGCD(x, y))
}

Improving TrivialGCD(), and the “and” and “or” keywords

In practice, we do not need to use two nested if statements to test whether p is a divisor of both a and b. Instead, we can test both statements as part of a single if statement using an and keyword, which in Go is represented by &&. If x and y are two Boolean expressions (i.e., evaluating to true or false), then the expression x && y is true precisely when both x and y are true; it is false otherwise.

We will use this idea to update our implementation of TrivialGCD() with a single if statement as follows.

func TrivialGCD(a, b int) int {
    d := 1
    m := Min2(a, b)
    for p := 1; p <= m; p++ {
        if a % p == 0 && b % p == 0 {
            d = p
        }
    }
    return d
}

Go also has an or keyword, represented by ||. The expression x || y is true precisely when at least one of x and y are true; it is false when both x and y are false. A truth table illustrating all four different outcomes for the “and” and “or” keywords is shown in the figure below.

Implementing Euclid’s nontrivial GCD algorithm

We now return to implementing Euclid’s algorithm. The pseudocode for EuclidGCD() is reproduced below.

EuclidGCD(a, b)
    while a ≠ b
        if a > b
            a ← a − b
        else
            b ← b − a
    return a 

The only aspect of this function that we have not yet introduced is the test for inequality of a and b, while a ≠ b. In a previous lesson, we introduced a collection of comparison operators. In particular, we saw that ≠ can be represented in Go using the operator !=. We use this operator in our implementation of EuclidGCD() below.

func EuclidGCD(a, b int) int {
    for a != b {
        if a > b {
            a = a - b
        } else { 
            b = b - a
        }
    }
    return a
}

Timing the two GCD algorithms

You may still be wondering what the big deal is. Is Euclid’s approach for finding a GCD really that much better? Aren’t modern computers so fast that they make this problem obsolete?

Let’s time TrivialGCD() and EuclidGCD() on the same inputs. The code that we will use for timing will prove handy throughout our programming future for measuring the efficiency of different functions.

First, we will add two package imports to the top of our code, so that our import statements are the following.

import (
    "time"
    "log"
)

In func main(), we declare two integer variables and set them to values that are on the order of a million; it would be better to use randomly generated integers, but we do not yet know how to generate random integers, and so we save that discussion for a later chapter.

func main() {
    x := 3782026
    y := 2731479
}

Next, we will time TrivialGCD(). First, we declare a variable named start that is equal to the current time using the built-in function time.Now(). This variable has its own special type, which we will return to discuss later. For now, think of declaring start as clicking the “start” button on a stopwatch.

func main() {
    x := 3782026
    y := 2731479

    //timing TrivialGCD
    start := time.Now()
}

We then will call TrivialGCD(x, y). We do not need the output of TrivialGCD(x, y), and so we will not set a variable equal to this output. (Don’t worry, Go’s compiler won’t get angry.)

func main() {
    x := 3782026
    y := 2731479

    //timing TrivialGCD
    start := time.Now()
    TrivialGCD(x, y)
}

Finally, we need to click the “stop” button on our conceptual stopwatch. To do so, we use the built-in function time.Since() from the time package, giving it our start variable as input so that it knows how long the process has been running. We store the result in a variable elapsed which will measure the time elapsed between calling time.Now() and time.Since().

func main() {
    x := 3782026
    y := 2731479

    //timing TrivialGCD
    start := time.Now()
    TrivialGCD(x, y)
    elapsed := time.Since(start)
}

We then simply need to print the value of elapsed in a clear format, which can be done with a log.Printf() statement.

func main() {
    x := 3782026
    y := 2731479

    //timing TrivialGCD
    start := time.Now()
    TrivialGCD(x, y)
    elapsed := time.Since(start)
    log.Printf("TrivialGCD took %s", elapsed)
}

We now will repeat this process and time EuclidGCD(), updating func main() as shown below. Note that we are very careful to run EuclidGCD() on the exact same input integers that we used for TrivialGCD(), and that we place only the call to EuclidGCD() between the lines invoking time.Now() and time.Since() so that we obtain accurate results.

func main() {
    x := 3782026
    y := 2731479

    //timing TrivialGCD
    start := time.Now()
    TrivialGCD(x, y)
    elapsed := time.Since(start)
    log.Printf("TrivialGCD took %s", elapsed)

    //timing EuclidGCD
    start2 := time.Now()
    EuclidGCD(x,y)
    elapsed2 := time.Since(start2)
    log.Printf("EuclidGCD took %s", elapsed2)
}

Furthermore, let’s see what happens as we make the numbers larger.

The previous question is hinting at a critical theme of programming, which is that the benefits of a faster algorithm provides tend to increase as the size of the input parameters increases. Computing the GCD of two small numbers may be relatively fast with either TrivialGCD() or EuclidGCD(). However, as we increase the size of the input integers to the order of 100 million, TrivialGCD() takes several seconds on a typical computer, while EuclidGCD() finishes in about a millionth of a second.

This phenomenon is illustrated in the following table, which illustrates the runtime of the two algorithms on input integers having different numbers of digits. We can quantify how much faster EuclidGCD() is by taking the ratio of the runtime of TrivialGCD() to EuclidGCD() on the same input; this ratio is called the speedup of EuclidGCD() compared to TrivialGCD(). As we continue to increase the size of the input integers, TrivialGCD() will start to exhaust considerable computational resources, whereas EuclidGCD() will finish in the blink of an eye.

As we move toward the final code-along in this introductory chapter, we are now ready to consider the second nontrivial algorithm of this chapter, the sieve of Eratosthenes. Will we see that it provides a considerable speedup as well?

Check your work from the code along

We provide autograders in the window below (or via a direct link) allowing you to check your work for the following functions:

• TrivialGCD()
• EuclidGCD()