Solving the Fibonacci Sequence with Matrix Exponentiation

This is a tutorial to find large fibonacci numbers using matrix exponentiation, speeded up with binary exponentiation.
The part where dynamic programming comes in, is when storing the 2th powers of the base matrix.

We do this using an array where each element is populated using the square of the last element. a[i]=a[i-1]^2.
The fibonacci sequence can be evaluated using the recursive matrix form as shown in this lecture. This lets us evaluate the Nth fibonacci term in O(logN)

References:
Fibonacci Numbers:
https://www.mathsisfun.com/numbers/fi...

Matrix exponentiation:
https://threads-iiith.quora.com/Solvi...
http://zobayer.blogspot.in/2010/11/ma...

Solving Recurrences:
http://fusharblog.com/solving-linear-...

Code Link: https://github.com/gkcs/Competitive-P...

#fibonacci #matrix-exponentiation #dynamic-programming