def gcd(a: int, b: int) -> int:
# The Euclidean Algorithm
#
# Use a while loop that continues as long as b is not 0.
# In each iteration:
# 1. Compute the remainder of a divided by b (hint: use the % operator)
# 2. Set a to the old value of b
# 3. Set b to the remainder
# When b becomes 0, a holds the GCD — return it.
pass # TODO: replace this line with your implementation16 The Concept of an Algorithm
In everyday life we constantly follow step-by-step procedures: cooking recipes, assembly instructions, or tying shoe laces. In computer science we formalise this idea with the concept of an algorithm.
16.1 Definition
An algorithm is a finite sequence of well-defined, unambiguous instructions that, given some input, produces an output in a finite number of steps.
16.2 Properties of an Algorithm
For a set of instructions to qualify as an algorithm, it must satisfy the following properties:
| Property | Meaning |
|---|---|
| Finiteness | The algorithm terminates after a finite number of steps. |
| Determinism | Each step has exactly one well-defined successor. |
| Definiteness | Every instruction is precise and unambiguous. |
| Input | The algorithm receives zero or more inputs. |
| Output | The algorithm produces at least one result. |
| Effectiveness | Every step can actually be carried out (is computable). |
16.3 Example: Tying Shoe Laces
An everyday example of an algorithm is tying shoe laces.
- Input: An untied shoe with two loose laces.
- Output: A tied shoe with a secure bow.
- Finiteness: The process ends once the bow is formed.
- Definiteness: Each step (cross laces, form loop, wrap around, pull through) can be described precisely.
- Determinism: Given the same starting position, the same steps always produce the same knot.
- Effectiveness: Every step involves a physical action that can be performed.
When you wrote instructions for your partner to tie a shoe, you experienced first-hand how important definiteness is: any vague step (“make a knot”) leads to confusion.
16.4 From Everyday Algorithms to Mathematical Algorithms
Algorithms are not limited to physical tasks. Many important algorithms operate on numbers. One of the oldest known algorithms is the Euclidean algorithm for computing the Greatest Common Divisor (GCD) of two integers.
The GCD of two integers is the largest positive integer that divides both numbers without a remainder.
Examples: - gcd(12, 8) = 4 (because 4 divides both 12 and 8) - gcd(48, 18) = 6 (because 6 divides both 48 and 18) - gcd(56, 15) = 1 (the numbers share no common factor other than 1)
16.5 The Euclidean Algorithm
The Euclidean algorithm computes the GCD by repeatedly replacing the larger number with the remainder of dividing the two numbers. The process continues until the remainder is zero. At that point, the other number is the GCD.
16.5.1 The Algorithm in Natural Language
- Given two positive integers a and b.
- Compute the remainder r = a mod b.
- Replace a with b and b with r.
- If b = 0, then a is the GCD. Stop.
- Otherwise, go back to step 2.
16.5.2 Checking the Algorithm Properties
- Input: Two positive integers a and b.
- Output: Their greatest common divisor.
- Finiteness: The remainder strictly decreases with each step, so the algorithm always terminates.
- Determinism: Each step is uniquely determined (compute remainder, swap values).
- Definiteness: “Divide a by b, take the remainder” is unambiguous.
- Effectiveness: Integer division and remainder are basic computable operations.
16.5.3 Worked Example: gcd(48, 18)
| Step | a | b | b * q + r | r |
|---|---|---|---|---|
| 1 | 48 | 18 | 18 * 2 + 12 | 12 |
| 2 | 18 | 12 | 12 * 1 + 6 | 6 |
| 3 | 12 | 6 | 6 * 2 + 0 | 0 |
After step 3, b = 0, so the GCD is a = 6.
16.5.4 Worked Example: gcd(56, 15)
| Step | a | b | b * q + r | r |
|---|---|---|---|---|
| 1 | 56 | 15 | 15 * 3 + 11 | 11 |
| 2 | 15 | 11 | 11 * 1 + 4 | 4 |
| 3 | 11 | 4 | 4 * 2 + 3 | 3 |
| 4 | 4 | 3 | 3 * 1 + 1 | 1 |
| 5 | 3 | 1 | 1 * 3 + 0 | 0 |
After step 5, b = 0, so the GCD is a = 1. The two numbers are coprime (they share no common factor other than 1).
16.6 Implementing the Euclidean Algorithm in Python
Now it is your turn to translate the algorithm into Python.
Recall the algorithm:
- Compute the remainder r = a mod b. (In Python:
a % b) - Replace a with b and b with r.
- If b = 0, return a (the GCD).
- Otherwise, repeat from step 1.
Hint: You will need a while loop that runs as long as b is not zero.
Task: Complete the function below so that it returns the GCD of two positive integers.
16.6.1 Testing Your Implementation
Run the cell below to check whether your gcd function produces the correct results.
16.7 Ways to Describe an Algorithm
In this notebook we described the Euclidean algorithm in three different ways:
| Notation | Example | Pros | Cons |
|---|---|---|---|
| Natural language | “Divide a by b and take the remainder …” | Easy to understand | Can be ambiguous |
| Table (trace) | Step-by-step table with values of a, b, r | Shows execution clearly | Only for specific inputs |
| Programming language | while b != 0: … |
Executable | Tied to one language |