Is there a faster way to compute the nth Fibonacci number than by fib2? Hint: On

Question

Is there a faster way to compute the nth Fibonacci number than by fib2? Hint: One idea involves matrices.

There exists a (log n) algorithm for computing the nth Fibonacci number that manipulates only integers. It is based on the equality

Fn-1        Fn                                 0          1   n

                                                  =                                      for n 1. (it is a matrix)

                  Fn         Fn+1                             1          1

Prove the equality.

Explanation / Answer

Interesting recurrence formula that can be used to find n’th Fibonacci Number in O(Log n) time

Fn-1        Fn                                 0          1   n

                                                  =                                      for n 1. (it is a matrix)

                  Fn         Fn+1                                1          1

Taking determinant on both sides, we get
(-1)n = Fn+1Fn-1 – Fn2
Moreover, since AnAm = An+m for any square matrix A, the following identities can be derived (they are obtained form two different coefficients of the matrix product)

FmFn + Fm-1Fn-1 = Fm+n-1

By putting n = n+1,

FmFn+1 + Fm-1Fn = Fm+n

Putting m = n

F2n-1 = Fn2 + Fn-12

F2n = (Fn-1 + Fn+1)Fn      ----> 1

F2n = (2Fn-1 + Fn)Fn                   -----> 2

To get the formula to be proved, we simply need to do following in the above 2 equations :-
If n is even, we can put k = n/2
If n is odd, we can put k = (n+1)/2

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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