20141027:TP:C:MoreVector:EN

Introduction

This session presents a series of classical exercise with array and vectors. The main goal is to train you with pointers again and again.

Arrays of floats

In this part we'll see some classical trap when dealing with arrays of float and a classical way to limit floating points errors.

We'll work in a file called float_array.c containing functions we want to implement and some tests with it. In order to compile this code you'll need to link with libm, which can easily be done by adding -lm to the LDLIBS variable of your Makefile.

Basic sum

The first function is pretty simple, it takes two pointers on float, the first one is the beginning of the array and the second one is the first address after the array. The functions thus computes the sum of float in the array.

/*
 * array_sum(begin, end)
 * Sum float in an array between begin (included) and end (excluded)
 */
float array_sum(float *begin, float *end);

You shall now test this function with the following main (we should have better tests later):

int main() {
  // Arrays of 2^25 floats
  float *tab = malloc((1<<25) * sizeof(float));
  // Fill it with 1
  for (float *cur = tab; cur != tab + (1<<25); ++cur)
    *cur = 1.0;
 
  // Print the theoretical value:
  printf("Sum should be: %g\n", (float)(1<<25));
 
  printf("array_sum: %g\n", array_sum(tab, tab + len));
 
  return 0;
}

• What do you get ? Is the result correct ? Try with a size of 2^24, is it correct now ?

Hints: floating point numbers often present what we call an absorption effect: small values are absorbed by bigger one. Thus, when doing the sum, the partial value can absorb the value of the current cell.

Divide and Conquer Sum

A strategy to solve the previous problem is to use an algorithm called Divide and Conquer. It's a recursive version of the sum where we only add a cell to another cell and then sum partial results of sub-array of the same size. Here is the principle of the algorithm:

dnc_sum(left, right)
  if right - left == 1 then
    return *left
  mid = left + (right - left) / 2
  return dnc(left, mid) + dnc(mid right)

The following function should implement this algorithm:

/*
 * array_recsum(begin, end)
 */
float array_recsum(float *begin, float *end);

• Compare the result of this algorithm with the previous one.

Divide and Conquer with Threshold

We now extend the previous algorithm with an other classical strategy: when the size of the array is less than a given threshold we use a classical linear sum (which is a little bit faster.)

Implement the following function:

/*
 * array_recsum2(begin, end)
 */
float array_recsum2(float *begin, float *end, long minsize);

Testing

The following code will test all your sum functions and compare the results.

// Play around arrays and float
 
# define _XOPEN_SOURCE 600
 
# include <math.h>
# include <stdio.h>
# include <stdlib.h>
 
/* Your functions goes here */
 
/* Tests */
 
void simple_test(size_t len) {
  // Allocate and fill a huge vector of float
  float                *vect;
  vect = malloc(len * sizeof (float));
  // Fill with 1
  for (float *cur = vect; cur != vect + len; ++cur)
    *cur = 1;
 
  printf("Simple tests:\n");
  printf("  Real sum: %g\n", (float)len);
  printf("  array_sum: %g\n", array_sum(vect, vect + len));
  printf("  array_recsum: %g\n", array_recsum(vect, vect + len));
  printf("  array_recsum2: %g\n", array_recsum2(vect, vect + len, 64));
 
  free(vect);
}
 
void random_test(size_t len) {
  // Allocate and fill a huge vector of float
  float                *vect;
  vect = malloc(len * sizeof (float));
  // Fill with random float number in [0;pi[
  for (float *cur = vect; cur != vect + len; ++cur)
    *cur = (((float)random()) / RAND_MAX) * acos(-1);
 
  printf("Random tests:\n");
  printf("  array_sum: %g\n", array_sum(vect, vect + len));
  printf("  array_recsum: %g\n", array_recsum(vect, vect + len));
  printf("  array_recsum2: %g\n", array_recsum2(vect, vect + len, 64));
 
  float                *vect2;
  vect2 = malloc(len * sizeof (float));
  // Fill with random float number in [0;pi[
  for (float *cur = vect2; cur != vect2 + len; ++cur)
    *cur = (((float)random()) / RAND_MAX) * acos(-1);
 
  printf("  array_sumproduct: %g\n", array_sumproduct(vect, vect2, len));
 
  free(vect);
}
 
// Array size: just change the exponent (25) to see the threshold of the absorption effect.
# define ARRAY_SIZE (1<<25)
 
int main() {
  simple_test(ARRAY_SIZE);
  random_test(ARRAY_SIZE);
  return 0;
}

Quick Sort

For this part, you'll implement a quick sort.

Here is the principle of the algorithm, it's made of 2 functions partition and quick_sort:

quick_sort(left, right)
  if left == right then
    return
  pivot = choose a point in the array
  pivot = partition(left, right, pivot)
  quick_sort(left, pivot)
  quick_sort(pivot + 1, right)

partition(left, right, pivot)
  move all values less than *pivot on the left and return the new position of the pivot.

In order to choose a good pivot you can:

• use the left bound
• use the right bound (-1 since right is excluded)
• use the middle of the array
• choose the median value between the three previous.

• Complete the following code

static inline
int* choose_pivot(int *left, int *right) {
  /* FIX ME */
}
 
/*
 * partition(left, right, pivot): push value less than *pivot on the left
 * return the new pivot.
 */
int* partition(int *left, int *right, int *pivot) {
  /* FIX ME */
}
 
/*
 * quick_sort(left, right)
 */
void quick_sort(int *left, int *right) {
  /* FIX ME */
}

In order to test your code, here is a set of tests:

// Quick Sort
 
# define _XOPEN_SOURCE 600
 
# include <assert.h>
# include <stdio.h>
# include <stdlib.h>
 
/* Your code goes here */
 
/* Tests */
 
static inline
int width(int i) {
  int           w = 0;
  for (; i > 0; i /= 10) w += 1;
  return w;
}
 
void print_array(int tab[], size_t len) {
  int           w = width(len - 1);
  for (size_t i= 0; i < len; ++i)
    printf("| %*zu ", w, i);
  printf("|\n");
  for (size_t i= 0; i < len; ++i)
    printf("| %*d ", w, tab[i]);
  printf("|\n");
}
 
static inline
int is_sorted(int *left, int *right) {
  int          *cur;
  for (cur = left + 1; cur != right && *(cur - 1) <= *cur; ++cur) {}
  return cur == right;
}
 
void test(int *tab, size_t len) {
  printf("Before sort:\n");
  print_array(tab, len);
 
  quick_sort(tab, tab + len);
 
  printf("After sort:\n");
  print_array(tab, len);
  assert(is_sorted(tab, tab + len));
}
 
void sorted_test(int *tab, size_t len) {
  for (size_t i = 0; i < len; ++i)
    tab[i] = i;
  printf("\n>> Sorted test <<\n");
  test(tab, len);
}
 
void rev_sorted_test(int *tab, size_t len) {
  for (size_t i = 0; i < len; ++i)
    tab[i] = len - i - 1;
  printf("\n>> Reverse Sorted test <<\n");
  test(tab, len);
}
 
void random_test(int *tab, size_t len) {
  for (size_t i = 0; i < len; ++i)
    tab[i] = random() % len;
  printf("\n>> Random test <<\n");
  test(tab, len);
}
 
// You can change the size
# define SIZE 10
 
int main() {
  int          *tab;
  tab = calloc(SIZE, sizeof (int));
  sorted_test(tab, SIZE);
  rev_sorted_test(tab, SIZE);
  random_test(tab, SIZE);
  free(tab);
  return 0;
}

BONUS: Ring Buffer

Want more ? Implement a queue as a ring buffer (using an array of fixed size), here are the expected operations:

struct ring_buffer {
  size_t        left, size, capacity;
  int          *buffer;
};
 
void init_ring_buffer(struct ring_buffer *buf, size_t capacity) {
  buf->size = buf->left = 0;
  buf->capacity = capacity;
  buf->buffer = calloc(capacity, sizeof (int));
}
 
int ring_push_back(struct ring_buffer *buf, int x);
int ring_pop_back(struct ring_buffer *buf, int *x);
int ring_push_front(struct ring_buffer *buf, int x);
int ring_pop_front(struct ring_buffer *buf, int *x);
 
// Printing from front value to back value
void print_ring(struct ring_buffer *buf) {
  printf("left: %zu\n", buf->left);
  printf("size: %zu\n", buf->size);
  printf("capacity: %zu\n", buf->capacity);
 
  for (size_t i = 0; i < buf->size; ++i)
    printf("| %d ", buf->buffer[(i + buf->left) % buf->capacity]);
  printf("|\n");
}

A ring buffer is a circular array: when moving after the last cell we wrap at the beginning and when moving before the first cell we wrap on the last cell. With this idea, operating on the front avoid shifting the rest of the array.