Exercise 1 shows that it is possible to compute xn in O(log N) time. This fact i

Question

Exercise 1 shows that it is possible to compute xn in O(log N) time. This fact in turn makes it possible to write an implementation of the function F ib(n) that also runs in O(log N) time, which is much faster than the traditional iterative version. To do so, you need to rely on the somewhat surprising fact that the Fibonacci function is closely related to a value called the golden ratio, which has been known since the days of Greek mathematics. The golden ratio, which is usually designated by the Greek letter , is defined to be the value that satisfies the equation 2 - - 1 = 0 Because this is a quadratic equation, it actually has two roots. If you apply the quadratic formula, you will discover that these roots are 1 + /2

Explanation / Answer

PS: Please rate the answer I have described the algorithm here - http://www.cramster.com/answers-feb-12/computer-science/question_2183823.aspx?rec=0 Program is here. #include void multiply(int F[2][2], int M[2][2]); void power(int F[2][2], int n); /* function that returns nth Fibonacci number */ int fib(int n) { int F[2][2] = {{1,1},{1,0}}; if(n == 0) return 0; power(F, n-1); return F[0][0]; } /* Optimized version of power() in method 4 */ void power(int F[2][2], int n) { if( n == 0 || n == 1) return; int M[2][2] = {{1,1},{1,0}}; power(F, n/2); multiply(F, F); if( n%2 != 0 ) multiply(F, M); } void multiply(int F[2][2], int M[2][2]) { int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; } /* Driver program to test above function */ int main() { int n = 9; printf("%d", fib(9)); getchar(); return 0; }

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.