# Find a Fibonacci Number with Matrix Exponentiation

### Core Concepts

1. We can represent any number with a power of (2 or 3 or anything). Evidence? The binary system 🙂
So we can represent any number with `log n` bits and using 2 as the exponent.
2. `f(n) = f(n-1) + f(n-2)` => `f(n) = 1*f(n-1) + 1*f(n-2)`
``````[f(n)] = |1 1| * |f(n-1)|
|f(n-2)|
``````

We should make the matrix a square because that would make matrix multiplication possible as a matrix exponent.
Eventually we need an exponential of the first matrix.

``````|   f(n) |   = | 1 1 | *  | f(n-1) |
| f(n-1) |     | 1 0 |    | f(n-2) |

|   f(n) |   = | 1 1 | *pow(n-1)   | f(1) |
| f(n-1) |     | 1 0 |             | f(0) |

``````
3. Use memoization. Get the Nth number. Represent the number as binary. e.g. `23`.
4. We need to calculate `23 -1 = 22nd` exponent. `22 = 10110`
5. We need f(0) * f(2) * f(4).

### Reference

Written with StackEdit.

This site uses Akismet to reduce spam. Learn how your comment data is processed.