CS209 lab8

CS209 lab8

http://www.maths.nuigalway.ie/~gettrick/teach/cs209/l8.html

For this lab you should submit all source code (C files), and the result(s) of running the program on (a few) test cases. The source code must be well presented (indenting, spaces, reasonable variable/function names, etc.) and must include comments (as a rough guideline - aim to have nearly as many comments as lines of code).
The above material should be uploaded in BLACKBOARD before the deadline of 5pm Wednesday 30th. March 2011. You will lose 20% for each day (or part of day) the lab is late.
Plagiarism (the unattributed copying of work from other sources (internet, fellow students,....)) will not be tolerated. Please see http://www.nuigalway.ie/engineering/documents/plagiarism_guide_students _v4.pdf. You risk getting zero for your lab if it is found to be plagiarized.

Consider the C program covered in lectures, that calculates the nth Fibonacci number in logarithmic time using binary powering: http://www.maths.nuigalway.ie/~gettrick/teach/cs209/progs/binFIB.c. Instead of using the (global) 2x2 matrix array, one can represent the matrix array (and any of its powers array², array⁴, array⁸, array¹⁶, etc.) by just storing 2 numbers, a and b, where the matrix will always have the form (first row: [a+b,b] second row:[b,a] ). Modify the program to use this fact.