CEG221: Advanced C Programming for Engineers

 

Midterm Project: Code Integration

 

Program Background:

Frequently, you will have a partial solution to an engineering problem - a library file (.LIB) and its accompanying header file (.h) that encapsulate functions, data structures, or both. This library can then be called from a program to perform complex operations. You don’t need to know how it works; just read the header file, which frequently contains documentation on how to use the functions and structures, and use it!

 

Last term, CEG 220 students implemented functions that performed addition, subtraction, and multiplication on matrices. The matrix, a double* in row major format (first row values stored, second row values stored, …, last row of values stored) needs two more critical operations to be a complete library: invert, and fastpow – all of which only work on square matrices.

 

FastPow for matrices is no different than pow for doubles – with one difference – taking log2(n) steps to do n multiplications. Here’s how it works for integers/doubles:

 

            Let’s compute cn; c is any number and n is the exponent. Using the following rules for exponents:

 

     (1) cn = (cn/2)2

     (2) cn = c*cn-1

 

            Now all we need is the recursive fast power algorithm:

            If n == 1, return n

            If n is even, use rule (1). Return square( c, n/2 ).

            If n is odd, use rule (2). Return c * fastpow(c, n-1).

 

            Example:

            Let’s take n to be 17. Using the traditional power method, computing cn takes 16 steps.

            Using the fast power method:

1)      17 is odd, so we return c * fastpow(c, 16)

2)      16 is even, so we return square( fastpow(c, 8), 2 ). Overall answer so far is: c * square( fastpow(c, 8), 2 )

3)      8 is even so we return square( fastpow(c, 4), 2). Overall answer so far is: c * square( square( fastpow(c, 4) ) )

4)      4 is even so we return square(fastpow(c, 2), 2). Overall answer so far is: c * square( square( square( fastpow(c, 2) ) ) )

5)      2 is even so we return square(fastpow(c, 1), 2). Overall answer so far is: c * square( square( square( square( fastpow(c, 1) ) ) ) )

6)      1 == 1, so we return n. Overall computation: c * square( square( square( square( n ) ) ) )

 

In the end, fastpow took 6 multiplications rather than 16.

 

NOTES:

·        The value of “1” for matrices is the identity matrix, which varies depending on the dimensions of the matrix

·        HINT: to make the algorithm work properly, we must add another base case – the case of computing c2.

 

Modified Algorithm:

            If n == 1, return c

            If n == 2, return c * c

            If n is even, use rule (1). Compute cn/2. Square it. Return that value.

            If n is odd, use rule (2). Compute cn-1. Return c * that value.

 

Analysis: Since we keep halving the amount of work being done, this algorithm takes log2(n) time given an exponent of n.

 

From here, we can replace “c” with a matrix, and we have a fast-power algorithm for matrices.

 

Since matrix multiplication is computationally intensive, we want to speed it up as much as possible. Since matrix multiplication requires n3 work to multiply an n x n matrix by another n x n matrix, it would take roughly 103 x 49 = 49,000 operations to multiply a 10 x 10 matrix by itself 50 times. However, if we can reduce the number of multiplications from n to log2(n), we can reduce it to 103 x 5.615 = 5,615 operations. A significant savings, especially when processor power is at a premium.

 

What You Need

1)      Microsoft VisualStudio 6.0 or Microsoft VisualC++ 6.0

2)      BasicMatrix.lib and BasicMatrix.h

3)      An empty project that links with BasicMatrix.lib available here

 

Your Task

1)      Implement fastPower() for matrices using the BasicMatrix library

 

Program Requirements:

1)      Your program must comply with the class programming standard

2)      You must submit a hand-written program specification

3)      You must submit a hard copy of source code, as well as a soft copy on disk on the due date

 

Grading Standard:

 

A Note on Grading: If your program does not compile or link, you will receive no credit for any programming-related parts of the project. However, you will receive credit for things such as documentation of code, correct style, etc. Also, it is incredibly important that you collaborate with your peers to learn from each other; remember that sharing ideas is permitted, but not code. Anyone found sharing code (this includes comments) will receive NO CREDIT for the assignment and may receive judicial action.

 

Due Date: