Assignment 3

This assignment consists of 2 pieces of code: one to compute vector dot product, the other to compute the (integer) power of a number via binary powering. There is also an optional bonus component regarding matrix product.

For all code in this assignment, no looping constructs (for, while, do) are to be used. Naturally, neither can goto!

Only the code for the functions below is to be handed in. You will need to write a mainline program to test your code, but do not hand it in. The bonus part, if done, should be handed in at the same time, also using WebCT as part of assignment 3.

Vector dot product

Write a function that given 2 vectors of doubles (implemented as arrays) and their lengths, return the dot product of the vectors. If one of the vectors is shorter than the other, assume that the "missing" entries are all 0. You may assume that the length will be positive (or zero). Use the following prototype for your function:

double dot_product(double *v1, int l1, double *v2, int l2);

Binary powering

Binary powering works as follows. Suppose you have to compute x¹⁹, where x is some floating point number. First, notice that 19 in binary is 10011. Instead of multiplying x with itself 19 times, notice that ((((x^2)^2)^2)*x)^2*x = x¹⁹. In general, this can be coded in C as

double binary_power(double x, int p) {
    double b,c;
    int n;

    b = 1.0;
    c = x;
    n = p;
    while (n != 0) {
        b *= (n & 1 == 1) ? c : 1;
        c *= c;
        n >>= 1;
    }
    return b;
}

Use the same prototype for your function as the one above.

Write a function that computes x^p using binary powering, but in a purely recursive manner.

Matrix product (optional bonus)

Write a function two compute the product of two matrices A and B recursively; however, assume that instead of having A and B, you only have A and the transpose of B (call it Bt). Your function should have the prototype

(double **) matrix_product(double **A, double **Bt, int m, int n, int p);

where Bt is the transpose of the matrix B. Assume that A is m by n, and B is n by p (so that Bt is p by n). You may assume that m, n, and p are all strictly positive. It is the responsibility of your function to allocate memory for the answer.

Hints:

re-use the code for the vector product written above.
you will need to define an auxiliary function to do this; this auxiliary function will actually be the one to recurse. This auxiliary function will have more parameters than matrix_product.

This bonus part is worth +8 points on the assignments component of your mark

Back to main page