Matrix exponentiation – Algorithmic Memoirs

Matrix exponentiation – Algorithmic Memoirs

What is matrix exponentiation?

Consider the Fibonacci series.

Recursively, it can be expressed as –

f (n) = f (n-1) + f(n-2) where f (1)=1, f (0)=0.

Now, if I were to ask you to calculate f (x) you could implement the simple recursive solution which solves for the value in O (2^x) — except that's terrible.

You'd be better off implementing an iterative solution, or perhaps even a memoizing solution in the case of multiple queries for solving the function.

Now, this alternative can get you the answer in O (x) but let's say I want better.

Read full article from Matrix exponentiation – Algorithmic Memoirs