---
tags: programming languages
---

(Part of the course *Programming Languages*)

# Greatest Common Divisor

Euclid's algorithm is one of the oldest ones we have, coming from Euclid's Elements, see Proposition 2 on page 196 of [this edition](https://farside.ph.utexas.edu/Books/Euclid/Elements.pdf).

Euclid's algorithm is interesting for many reasons, not least how it links up geometry with algebra and programming, see [my video](https://youtu.be/ZcJMj0antos) on this. Anyway, here it is:

> `gcd(a,b)`:
>
> Input: Two whole numbers (integers) called `a` and `b`, both greater than `0`.
>
> (1) if `a>b` then replace `a` by `a-b` and go to (1).
> (2) if `b>a` then replace `b` by `b-a` and go to (1).
>
> Output: `a`.

(As usual, this algorithm is to be read in a top down manner, line by line, unless there is an explicit instruction to jump.)

**Activity:** Implement this algorithm in one or more of your favourite programming languages.

## <font color=red>Homework (Week 1)</font>

(Deadline: The Sunday following Week 2)

The aim of this homework is to familiarize yourself with LaTeX and to practice the computational model of equational reasoning.

- Read my notes on how to write a report. Start from the template `report.tex`. Submit in Canvas a link to the file `report.pdf` in the private Github repo that you previously shared with me.
- Use the `\begin{align*} ... \end{align*}` environment of Latex to write out the computation of `gcd(9,33)` similarly to how we have done the computation of $fib(6)$ in class (but write out the full computation without leaving any `...`.)

**Hint:** The Latex code for

\begin{align}
fib(6) & = fib(4) + fib(5)\\
& = fib(2) + fib(3) + fib(5)\\
& \ldots \\
& = 8
\end{align}

is

\begin{align*}
fib(6) & = fib(4) + fib(5)\\
& = fib(2) + fib(3) + fib(5)\\
& \ldots \\
& = 8
\end{align*}