Description

G(1) = 1
G(2) = 1
G(n) = aG(n − 1) + bG(n − 2) + c, ∀n > 2
In this assignment, you have to G(n) mod m using all the 3 ways taught in class, namely the recursive method, the iterative method and the matrix powering method. You have to submit the problem on the online judge, which will be set up shortly. There will be multiple test cases in the question. You have to take the number of test cases as input. For each test case, you have to take the parameters a, b and c and the numbers n and m, and print G(n) mod m. It is given that a,b,c,m ≤ 109 and n ≤ 1018. The languages allowed would be C or C++.
You need to write a report that contains the following:
1. The following table filled in with the appropriate values of n.
Time taken to compute G(n) mod m (in seconds) 10−5 10−4 10−3 10−2 10−1 1 10
Max value of n for recursive algorithm
Max value of n for iterative algorithm
Max value of n for matrix method
If the value of n exceeds 1018, just write > 1018 in the table.
2. The report must also contain the following plots, with appropriate data points and scale :
• Plot of the logarithm of the time taken by the recursive algorithm versus n
• Plot the time taken by the iterative algorithm versus n
• Plot the time taken by the matrix method algorithm versus the logarithm of n
3. Give a one or two paragraph writeup explaining the results obtained above.