## 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

function that `Min2()`

uses as a subroutine. We reproduce the Go implementation of `TrivialGCD()`

`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

, but we must first determine how to implement the line that tests whether `TrivialGCD()`

`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

with a single if statement as follows.`TrivialGCD()`

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

is `x || y`

precisely when at least one of `true`

`x`

and `y`

are `true`

; it is

when both `false`

`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.

`x` | `y` | `x && y` | `x || y` |

`true` | `true` | `true` | `true` |

`true` | `false` | `false` | `true` |

`false` | `true` | `false` | `true` |

`false` | `false` | `false` | `false` |

STOP:Say that we replaced the line`if a % p == 0 && b % p == 0 {`

in`TrivialGCD()`

with the incorrect line`if a % p == 0 || b % p == 0 {`

. What would the function return instead of the GCD?

Note:A common pitfall for introductory programmers is ensuring that both statements connected by a logical connective like`must be syntactically correct statements in the language. For example, the expression`

`&&`

`if a % p && b % p == 0 {`

would produce a compiler error in Go because although it may make sense to a human, Go views the expression`as an integer, whereas this statement must produce a Boolean value.`

`a % p`

### 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

and `TrivialGCD()`

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.`EuclidGCD()`

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

. This variable has its own special type, which we will return to discuss later. For now, think of declaring `time.Now()`

`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

from the `time.Since()`

package, giving it our `time`

variable as input so that it knows how long the process has been running. We store the result in a variable `start`

`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) }

STOP:Compile and run this code, either on your computer or by using the window below. What do you find?

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) }

STOP:Compile and run this code, either on your computer or by using the window below. How do the two approaches compare?

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

STOP:Add a digit to each of`x`

and`in your code. How does it affect the runtime of the two algorithms? What about if you add two digits?`

`y`

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.

Number of Digits | `TrivialGCD()` Runtime | `EuclidGCD()` Runtime | Speedup |

6 | 4.16 ms | 907 ns | 4,587 |

7 | 28.1 ms | 798 ns | 35,213 |

8 | 1.81 s | 871 ns | 2,078,071 |

9 | 7.31 s | 920 ns | 7,945,652 |

10 | (Times out in online IDE) | 910 ns | Unknown |

**Figure:**A table showing sample runtimes of

`TrivialGCD()`

and `EuclidGCD()`

for two integers having an indicated number of digits. The final column shows the “speedup” offered by `EuclidGCD()`

, which is the ratio between the runtime of `TrivialGCD()`

and `EuclidGCD()`

. Observe that the speedup increases as the size of the input increases.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()`