Fibonacci Numbers

The Fibonacci sequence is defined as follows: F_0 = 0, F_1 = 1,

F_n = F_{n-1} + F_{n-2}

The first elements of the sequence (OEIS A000045) are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

1. Fibonacci Coding

We can use the sequence to encode positive integers into binary code words. According to Zeckendorf’s theorem, any natural number n can be uniquely represented as a sum of Fibonacci numbers:

N = F_{k_1} + F_{k_2} + … + F_{k_r}
1 = 1 = F_2 = (11)_F
2 = 2 = F_3 = (011)_F
6 = 5 + 1 = F_5 + F_2 = (10011) _F
8 = 8 = F_6 = (000011) _F
9 = 8 + 1 = F_6 + F_2 = (100011) _F
19 = 13 + 5 + 1 = F_7 + F_5 + F_2 = (1001011) _F

The encoding of an integer n can be done with a simple greedy algorithm:

1. Iterate through the Fibonacci numbers from the largest to the smallest 
until you find one less than or equal to n.

2. Suppose this number was F_i. Subtract F_i from n and put a 1 in the i-2 
position of the code word (indexing from 0 from the leftmost to the 
rightmost bit).

3. Repeat until there is no remainder.

4. Add a final 1 to the codeword to indicate its end.

To decode a code word, first remove the final 1. Then, if the i-th bit 
is set (indexing from 0 from the leftmost to the rightmost bit), sum  
$F_{i+2}$  to the number.

2. Formulas for the nth Fibonacci number

Fibonacci in linear time

The n-th Fibonacci number can be easily found in O(n) by computing the numbers one by one up to n. However, there are also faster ways, as we will see.

We can start from an iterative approach, to take advantage of the use of the formula F_n = F_{n-1} + F_{n-2}, therefore, we will simply precalculate those values in an array. Taking into account the base cases for F_0 and F_1 .

Matrix form

It is easy to prove the following relation:

|0 1|^n = |Fn-2 Fn-1|
|1 1|     |Fn-1 Fn  |

Thus, in order to find 
F_n in O(log n) time, we must raise the matrix to n. 

void mat_mul(vector<vector<ll>>&mat1, vector<vector<ll>> &mat2){
    vector<vector<ll>> newmat(2, vector<ll>(2, 0));
    for(ll i=0;i<2;i++)
        for(ll j=0;j<2;j++)
            for(ll k=0;k<2;k++) newmat[i][j] += mat1[i][k]*mat2[k][j];
        
    mat1 = newmat;
}

ll fib(ll n){
    if(n==1) return 0;
    if(n==2) return 1;
    if(n==3) return 1;
    vector<vector<ll>> resmat, mat;
    resmat = mat = {{0, 1}, {1, 1}};
    ll i;
    n-=3;
    for(i=0;(1ll<<i)<=n;i++){
        if(n&(1ll<<i)) mat_mul(resmat, mat);
        mat_mul(mat, mat);
        //cout << mat[0][0] << mat[0][1] << mat[1][0] << mat[1][1];
    }
    return resmat[1][1];
}