In this assignment, you are given the cpp file HW2.cpp, which contains a prototype of the class Mat22. Basically, the class is a structure for 2 by 2 matrices the integers a,b,c, and d represent the matrix | a b c d |. The class should support several matrix operations, such as addition, multiplication, and fast exponentiation. The class will be used to implement the fast method that computes Fibonacci sequence as we discuss in the lectures.

We specify the details in the following tasks. You must submit only a single cpp file.

Task 1: Implement the constructors and the assignment operator. The specification is clear as described in the comments.

Task 2: Implement the operator overloading for the following three arithmetic operations +, , . Your code should implement the functionalities as below:

|a1 b1 c1 d1 |+ |a2 b2 c2 d2 | = |a1 + a2 b1 + b2 c1 + c2 d1 + d2 | ,

| a1 b1 c1 d1 | |a2 b2 c2 d2 |= | a1a2 + b1c2 a1b2 + b1d2 c1a2 + d1c2 c1b2 + d1d2 | .

The operation for subtraction is similar to the addition.

Note: it is possible to finish this task without math backgrounds of matrices. Just follow the rules defined here.

Task 3: Implement the display function (that prints the matrix). Then implement operator overloading for >> and <<. It is your choice to design how to print/cin a matrix.

Task 4: Implement the method fastexp that takes in input n returns a matrix that is n-th power of the original matrix. Let A be a 2 by 2 matrix. Given the multiplication rule as defined above, we can further define exponentiation as An = A A A (n times of multiplications of the matrix itself). You are going to implement the fast exponentiation method as discussed in the lecture. Your running time must be within O(log n).

Note: matrix multiplication has associativity, i.e. (AA)A = A(AA), and more generally, A (B C) = (A B) C. This is the same as integer multiplication. If you understand fast exponentiation for integers as we discuss in the class, this problem should be an easy generealization.

Task 5: Implement the function FastFib that on input n outputs the n-th term of the Fibonacci number. Your running time must be within O(log n) by using the method we discuss in the class. The Fibonacci numbers are defined as fn = { 1 n = 1, 2

fn1 + fn2 n 3 . Here you can assume that there is no integer overflow.

Task 6: In your main function, you should write some test cases to test your codes in the above tasks. The format is flexible

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include

using namespace std;

class Mat22

{

//the class for 2 by 2 matrices

public:

Mat22(); // default constructor

Mat22(int a,int b, int c, int d); // set the matrix as the input

Mat22(const Mat22 &b); // copy constructor

void operator=(const Mat22 &b); // assignment operator

Mat22 operator+(const Mat22 &b);// add two matrices

Mat22 operator-(const Mat22 &b);// similar as above

Mat22 operator*(const Mat22 &b);// matrix multiplication

Mat22 fastexp(int n);// compute matrix to the power of n

void display(ostream &out);// print the matrix, whatever way you like

as long as it makes sense

void input(ifstream &in)//use in to get user input for the matrix

private:

int a,b,c,d;// store matrix [a,b]

// [c,d]

};

//implement operator<< and operator>> so that the following operations are

possible

// cout << a and cin >> a

// make sure they can be chained

int FastFib(int n);//implement the Fast Fibonacci function

int main()

{

return 0;

}