Chapter 2

This chapter is an introductory chapter used to justify the use of C as the languaged used in this book. Post that, it goes over a single example with the purpose of introducing the C programming language to the reader.

Example: Euclid's Algorithm

To begin, we'll consider a C program to solve a classic elementary problem: "Reduce a given fraction to its lowest to its lowest terms." We want to write 2/3, not 4/6, 200/300. or 178468/267702. Solving this problem is equivalent to finding the greatest common divisor (gcd) of the numerator and the denominator: the largest integer which divides them both. A fraction is reduced to lowest terms by dividing both numerator and denominator by their greatest common divisor. An effective method for finding the greatest common divisor was discovered by the ancient Greeks over two thousand years ago: it is called Euclid's algorithm because it is spelled out in Euclid's famous treatise Elements.

Euclid's method is based on the fact that if u is greater than v then the greatest common divisor of u and v is the same as the greatest common divisor of v and u - v. This observation leads to the following implementation in C:

#include <stdio.h>

int gcd(int u, int v)
{
  int t;
  while (u > 0)
    {
      if (u < v)
	{ t = u; u = v; v = t; }
      u = u -v;
    }
  return v;
}

main()
{
  int x, y;
  while (scanf("%d %d", &x, &y) != EOF)
    if (x>0 && y >0)
      printf("%d %d %d\n", x, y, gcd(x,y));
}

Here is the implementation written in Rust:

use std::io;

fn gcd(mut u: u32, mut v: u32) -> u32 {
    let mut t;
    while u > 0 {
        if u < v {
            t = u;
            u = v;
            v = t;
        }
        u = u - v;
    }
    v
}

fn main() {
    for line in io::stdin().lines() {
        let elements: Vec<u32> = line
            .unwrap()
            .split(" ")
            .map(|x| x.parse::<u32>().expect("unable to parse string into i32"))
            .collect();

        match elements.len() {
            2 => {
                if elements[0] > 0 && elements[1] > 0 {
                    println!(
                        "gcd({}, {}) => {}",
                        elements[0],
                        elements[1],
                        gcd(elements[0], elements[1])
                    );
                }
            }
            _ => println!("The string must be two integers separated by a space"),
        }
    }
}

Notes:

I am not the best with C syntax, but there are some things that we need to cover for both C and Rust before moving on:

Copying

  1. In C, functions create local copies of their arguments, so even though x and y are passed into the gcd, their original values are not modified because u and v are not references to x and y.

This is why we can write printf("%d %d\n", x, y, gcd(x,y)). In theory, the gcd call gets evaluated before the printf call, so, if x and y were references and not copies, their updated values would have been printed in the printf call.

The Rust code is doing the exact same thing, but the mechanics of why it is happening are slightly different.

println!(
	"gcd({}, {}) => {}",
    elements[0],
    elements[1],
    gcd(elements[0], elements[1])
);

Rust has Ownership, which can be summed up as follows:

  • Each value in Rust has an owner.
  • There can only be one owner at a time.
  • When the owner goes out of scope, the value will be dropped.

In general, this means that variables passed to functions and methods or also passing ownership over those varables to functions and methods. I am not sure how things are handled with println! because that is a macro, but, the point remains that if element[0] and element[1] are passed to gcd and gcd gets evaluated first, then the println! macro should have printed the updated values for elements[0] and elements[1], right? Also, based off the rules of Ownership, it seems like we cannot have two versions of elements[0] and elements[1] around. So, what is going on?

The answer is the Copy Trait. The docs cover a lot, but the gist is that if a struct implements the Copy Trait, then instead of moving into the function (the transfer of ownership) it will implicitly create a copy of itself and pass that into the function. The data type u32 implements that Copy Trait, so ownership over elemtns[0] and elements[1] was never transfered because they were never moved.

scanf

We do not have scanf in Rust. As a result, I had to scan and parse the input myself, which led to a lot of extra code being added to the main function.

Thoughts

I really appreciated seeing gcd implemented using subtraction. Previously, I have only seen it implemented using remainder operators or mod operators, which have a direct relationship to subtraction, but I never think of them being on the same level. For example, I can understand someone not knowing modular arithmetic, but I would be completely surprised if they did not know how to subtract. So, for me, seeing this implemented using subtraction is a suble remnder that all this stuff can be written in such basic forms that it is hard to imagine anything of this stuff every being "difficult".