Lab5 - Algorithm Selection

In this lab, we will look at how algorithms affect program execution and compile time. To understand this, I will use digital sound as an example. First, calculate the execution time using the Clock object in the sample code on aarchie server.

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <time.h>
#include "vol.h"

// Function to scale a sound sample using a volume_factor
// in the range of 0.00 to 1.00.
static inline int16_t scale_sample(int16_t sample, float volume_factor) {
    return (int16_t) (volume_factor * (float) sample);
}

int main() {

    // Allocate memory for large in and out arrays
    int16_t*    in;
    int16_t*    out;
    in = (int16_t*) calloc(SAMPLES, sizeof(int16_t));
    out = (int16_t*) calloc(SAMPLES, sizeof(int16_t));

    int        x;
    int        ttl;

    clock_t start, end;
    float ftime;

    // Seed the pseudo-random number generator
    srand(-1);

    // Fill the array with random data
    for (x = 0; x < SAMPLES; x++) {
        in[x] = (rand()%65536)-32768;
    }

    start = clock();

    // ######################################
    // This is the interesting part!
    // Scale the volume of all of the samples
    for (x = 0; x < SAMPLES; x++) {
        out[x] = scale_sample(in[x], 0.75);
    }
    // ######################################

    end = clock();

    // Sum up the data
    for (x = 0; x < SAMPLES; x++) {
        ttl = (ttl+out[x])%1000;
    }

    ftime = (float)(end - start) / CLOCKS_PER_SEC;

    // Print the sum
    printf("Result: %d\n", ttl);
    printf("Runing Time: %f sec.\n", ftime);

    return 0;

}

The result obtained by executing the above source is shown in the figure below.

Now let's expand the source and test it. The second test is as follows.
1. Pre-calculate a lookup table (array) of all possible sample values multiplied by the volume factor, and look up each sample to get the scaled values.

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <time.h>
#include "vol.h"

// Function to scale a sound sample using a volume_factor
// in the range of 0.00 to 1.00.
static inline int16_t scale_sample(int16_t sample, float volume_factor) {
    return (int16_t) (volume_factor * (float) sample);
}

int main() {

    // Allocate memory for large in and out arrays
    int16_t*    in;
    int16_t*    out;
    in = (int16_t*) calloc(SAMPLES, sizeof(int16_t));
    out = (int16_t*) calloc(SAMPLES, sizeof(int16_t));

    int16_t* lookUp = calloc(65536, sizeof(int16_t));

    int        x;
    int        ttl;

    clock_t start, end;
    float ftime;

    // Seed the pseudo-random number generator
    srand(-1);

    // Fill the array with random data
    for (x = 0; x < SAMPLES; x++) {
        in[x] = (rand()%65536)-32768;
    }

    for (x = 0; x < 65536; x++) {
        lookUp[x] = (x - 32768) * 0.75;
    }

    start = clock();

    // ######################################
    // This is the interesting part!
    // Scale the volume of all of the samples
    for (x = 0; x < SAMPLES; x++) {
        out[x] = (lookUp[in[x] + 32768]);
    }
    // ######################################

    // Sum up the data
    for (x = 0; x < SAMPLES; x++) {
        ttl = (ttl+out[x])%1000;
    }

    end = clock();

    ftime = (float)(end - start) / CLOCKS_PER_SEC;

    // Print the sum
    printf("Result: %d\n", ttl);
    printf("Runing Time: %f\n sec.", ftime);

    return 0;

}

Finally, the test contents are as follows.
2. Convert the volume factor 0.75 to a fix-point integer by multiplying by a binary number representing a fixed-point value "1". For example, you could use 0b100000000 (= 256 in decimal) to represent 1.00. Shift the result to the right the required number of bits after the multiplication (>>8 if you're using 256 as the multiplier).

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <time.h>
#include "vol.h"

// Function to scale a sound sample using a volume_factor
// in the range of 0.00 to 1.00.
static inline int16_t scale_sample(int16_t sample, float volume_factor) {
    return (int16_t)(volume_factor * (float)sample);
}

int main() {

    // Allocate memory for large in and out arrays
    int16_t*    in;
    int16_t*    out;
    in = (int16_t*)calloc(SAMPLES, sizeof(int16_t));
    out = (int16_t*)calloc(SAMPLES, sizeof(int16_t));

    int16_t* lookUp = calloc(65536, sizeof(int16_t));

    int        x;
    int        ttl;

    clock_t start, end;
    float ftime;

    // Seed the pseudo-random number generator
    srand(-1);

    // Fill the array with random data
    for (x = 0; x < SAMPLES; x++) {
        in[x] = (rand() % 65536) - 32768;
    }

    start = clock();

    // ######################################
    // This is the interesting part!
    // Scale the volume of all of the samples
    for (x = 0; x < SAMPLES; x++) {
        out[x] = (int16_t)(in[x] * 0.75 * 256) >> 8;
    }
    // ######################################

    end = clock();

    // Sum up the data
    for (x = 0; x < SAMPLES; x++) {
        ttl = (ttl + out[x]) % 1000;
    }

    ftime = (float)(end - start) / CLOCKS_PER_SEC;

    // Print the sum
    printf("Result: %d\n", ttl);
    printf("Runing Time: %f\n sec.", ftime);

    return 0;

}

Let's compare the three tests at the same time.

Comparing the three tests, the second test was the slowest. The third test is not much different from the first. The third is the most optimized source.