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.

Vishal

A voyager on the journey to technology and art of software development. Pursuing arts, music, photography, and ways to live life on the edge

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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