Back to main

Exercise 11: Timing and static global variables

Background

To keep track of time, computers need something to measure it against. In C on the lab computers, we get the number of seconds since 00:00:00 UTC on 1 January 1970.

As you might imagine, this produces a fairly large number -- it exceeds the bounds of a normal int. We therefore use a long int, which has twice the number of bits of a normal int. Our time.h library also defines a special data type to store the time value: time_t. On our computers, this is the same as a long int.


We have seen how to pass information to and from functions with arguments and return values. Another way to share information is via static global variables. These variables are valid within the entire .c file.

Using global variables is generally bad programing practice, because it increases the complexity of programs, which in turn make it harder to debug. However, they are required for your second-year computer architecture course, so we present them here.

Technical details

Getting the time:

#include <stdio.h>
#include <time.h>  // extra include

int main() {
    time_t now;
    now = time(NULL);

    long int a = now;
    printf("%li\n", now);
}

Static variable:

#include <stdio.h>

static int shared_x;

void f() {
    int x = 3;
    shared_x = x + 1;
}

void g() {
   shared_x++;
}

int main() {
    f();
    g();
    printf("%i\n", shared_x);
}

Your task...

Modern computers can perform an amazing number of computations in a second. But are all computations the same? Let's measure the time it takes to do: + - * / for int.


(optional: repeat this experiment with float instead of int.)

... show your work to a demonstrator



Exercise 14: ncurses.h

Background

So far we have seen the boring printf, which does not allow us to move the cursor around. Using the additional ncurses library, we can print to arbitrary places on the screen.

Since this is an additional library, not part of the standard C libraries, we must tell the computer to include the library. The #include <ncurses.h> tells the computer to add the .h header file, but this unfortunately does not tell the computer to add the compiled library to the linking process. To do the latter, we must add -lncurses to our gcc command.

Technical details

Here is a minimal program with ncurses.h which does not print anything.

To compile it, you must add a -lncurses to your command-line:
gcc -o drawing.exe drawing.c -lncurses
#include <ncurses.h>

// you don't need to understand this function
void initscreen(void)
{
    initscr();
    raw();
    noecho();
    keypad(stdscr, TRUE);
}

int main(int argc, char *argv[])
{
    initscreen();

    // insert stuff here



    // ensure the screen is drawn
    refresh();

    // wait for a keypress
    int key = getch();
    endwin();
}

The previous example only waited for a keypress. Try adding the below code fragment to print out a few characters. What do the numbers do? Which is horizontal, and which is vertical?

// print characters.  Note the single quotes!
mvaddch(5, 1, 'a');
mvaddch(1, 5, 'b');
mvaddch(9, 20, '*');
mvaddch(0, 0, '_');

We can also print out strings:

// print a string: note the double quotes!
mvprintw(5, 5, "kittenz rock!");

To move the curor independently of printing something, or to print a character or string without moving the cursor, do:

move(10, 3);
addch('G');
printw("Bad dogs are bad.");

Your task...

The Flag of Scotland (also known as "Saint Andrew's Cross" and "the Saltire") has a blue background with a white diagonal cross.

Write a program which draws this in ncurses.


(optional: the background should be blue ("Pantone 300", or #0065bd in RGB), and the cross should be white. Look up how to use colours in ncurses online)

... show your work to a demonstrator


Exercise 15: Recursion

Background

To understand recursion, you must first understand recursion.

I therefore won't explain anything here.

Technical details

Here's a popular children's song in North America (no, I don't know why this gets taught to 6-year olds). Note that recursion is fairly pointless in this example (just use a for loop!), but it serves as a simple example of a function calling itself.

#include <stdio.h>

void bottles(int x) {
    printf("%i bottles of beer on the", x);
    printf(" wall, %i bottles of beer", x);
    printf("!\nTake one down, ");
    x--;
    printf("pass it around,\n");

    // stopping condition
    if (x == 0) {
        printf("no more bottles of ");
        printf("beer on the wall.\n");
        return;  // quit
    }
    printf("%i bottles of ", x); 
    printf("beer on the wall.\n\n");
    bottles(x);  // recursion
}

int main() {
    bottles(9);
}

Euclid's algorithm for calcuating the greatest common divisor. Try following the program on paper (i.e. figure out exactly what each variable is, keep track of all the function calls, etc). You may find it helpful to uncomment the DEBUG printf.

#include <stdio.h>

// Euclid's algorithm
int gcd(int a, int b) {
    //printf("DEBUG: gcd(%i, %i)\n", a, b);

    // stopping condition
    if (b==0) {
        return a;  // quit
    } else {
        return gcd(b, a % b);  // recursion
    }
}

int main() {
    int x = 57;
    int y = 76;
    int g = gcd(x,y);
    printf("Great Common Divisor of ");
    printf("%i and %i is: %i\n", x, y, g);
}

Your task...

Option 1: boring

Recall the Fibonacci sequence from Exercise 9 Arrays. Write a function which takes one input (n) and returns the nth numbers in the Fibonaci sequence -- without using an array to store all the intermediate values.

Option 2: fun, but hard

The Cantor ternary set is a mathematical construct which helped lay the foundations of topology. It is constructed by taking a line segment and removing the middle third:

In beautiful text rendering, it looks like this:

*********************************************************************************
***************************                           ***************************
*********         *********                           *********         *********
***   ***         ***   ***                           ***   ***         ***   ***
* *   * *         * *   * *                           * *   * *         * *   * *

Write a program which draws the first 5 iterations of the Cantor ternary set (as shown above).

... show your work to a demonstrator