6. Greatest Common Divisor¶

This time our goal is it to create a new project which allows us to do computations with rational numbers. C++ provides no built-in type able to store the value of a rational number. Instead C++ provides floating-point values which are able to approximate the value of rational numbers. For example, the value \(\frac{1}{3}\) cannot be represented by a floating-point value exactly.

In this lecture, we will not be fast enough to actually implement a new structure for rational numbers. Instead we think about an algorithm to compute the greatest common divisor (GCD). The GCD is needed to shorten a rational number after operations like addition or multiplication.

As before, the basic project structure will consist of three files, namely main.cpp, rational.hpp, and rational.cpp. So make sure to set it up properly.

$ pwd
/home/lyrahgames/projects/cpp-course
$ ls
01-hello  02-input  03-fibonacci  04-files
$ mkdir 05-rational
$ ls
01-hello  02-input  03-fibonacci  04-files  05-rational
$ cd 05-rational
$ pwd
/home/lyrahgames/projects/cpp-course/05-rational
$ touch main.cpp
$ touch rational.hpp
$ touch rational.cpp
$ ls
main.cpp  rational.hpp  rational.cpp

Euclid's Algorithm¶

Mathematically spoken, the function of the GCD, which we are calling \(\mathrm{gcd}\), can be defined by a recursive relation as follows.

One of the most popular algorithms to compute the GCD was proposed more than two thousand years ago by Euclid. Actually, Euclid has constructed two different algorithms based on modulo and subtraction respectively. We will restrict our implementation to the modulo-based method. As always, first, we start with the declaration of our own implementation. We want to take two natural numbers and output the GCD which is also a natural number.

// rational.hpp
unsigned int gcd(unsigned int x, unsigned int y);

After copying this line into the rational.cpp source file, we have to add the actual implementation. Here, we do not want to talk about the mathematical details. I recommend to read through the according Wikipedia article.

// rational.cpp
unsigned int gcd(unsigned int x, unsigned int y){
  while(y != 0){
    auto tmp = y;
    y = x % y;
    x = tmp;
  }
  return x;
}

Afterwards, let us use the newly created function inside the main.cpp source file.

// main.cpp
#include <iostream>
#include <rational.hpp>

using namespace std;

int main(){
  for (int i = 1; i < 20; ++i)
    for (int j = 1; j < 20; ++j)
        cout << "gcd(" << i << ", " << j << ") = " << gcd(i,j) << '\n';
}

The project can be compiled by the following command.

g++ -o rational main.cpp rational.cpp -I.

Include Guard¶

In larger projects, a C++ header file will typically be included in different source files to provide necessary function declarations and other structures for in- and external use. Assume that in our main.cpp we would like to include the files A.hpp and B.hpp. Furthermore, let B.hpp include the file A.hpp. As a result from compiling the main.cpp file, the preprocessor will first insert the contents of the files A.hpp and B.hpp into the main.cpp file. At this point another #include <A.hpp> directive is left from file B.hpp. Therefore the preprocessor has to run one more time and will include the file A.hpp a second time into the main.cpp file. According to the one-definition rule (ODR), this may lead to errors in the compilation process because of multiple occurrences of structures that should only appear once. To prevent this kind of behavior, we will use a #pragma once directive at the start of every header file.

// rational.hpp
#pragma once

unsigned int gcd(unsigned int x, unsigned int y);

Inline¶

Sometimes a function may be too small in its implementation to feasibly separate it into a declaration and definition. To lighten up the development process, we would like to provide function definitions inside a header file, like in the following example.

// rational.hpp
unsigned int gcd(unsigned int x, unsigned int y){
  while(y != 0){
    auto tmp = y;
    y = x % y;
    x = tmp;
  }
  return x;
}

But due to the one-definition rule (ODR), if at least two source files include the given rational.hpp header file, an error has to occur because the function gcd would be defined in more than one source file. This is a difference to the above discussion about the #pragma once directive. This time we are talking about that a definition is only allowed to occur one single time in the whole project concerning all source and header files. We can loosen up this strict rule by using the C++ keyword inline on our function.

// rational.hpp
inline unsigned int gcd(unsigned int x, unsigned int y){
  while(y != 0){
    auto tmp = y;
    y = x % y;
    x = tmp;
  }
  return x;
}

The C++ specifier inline allows us to define the same function, in other words the interface or implementation must not change, in multiple source files but in each file the definition is only allowed to occur once. Practically spoken, with inline we can define a function inside a header file regardless of how many times we are including the file in different source files.

Exercises¶

• Install the build2 build system toolchain according to the instructions.
• Read the sections 1.1 and 1.3 in the Pro Git book to understand the purpose of a version control system (VCS).

References¶

• https://en.wikipedia.org/wiki/Euclidean_algorithm
• https://en.cppreference.com/w/cpp/numeric/gcd
• https://git-scm.com/book/en/v2
• https://build2.org/install.xhtml