Category Archives: algorithm

Fibonacci Numbers in CC++

In mathematics, Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence:

fibonacci_1

or:

fibonacci_2

In mathematical terms, the Fibonacci sequence Fn is defined by the recurrence relation

fibonacci_3

with seed values

fibonacci_4

Our task is to write a function that returns Fn. Following are different methods to get the nth Fibonacci number

Method 1: Simple and Naive Recursion

A simple recursion that implementing the Fibonacci definition above.

int fib(int n)
{
    if (n <= 1) {
        return n;
    }
    return fib(n-1) + fib(n-2);
}

Time complexity: T(n) = T(n-1) + T(n-2) which is exponential.

This implementation does a lot of repeated work (see below).

fib(5)   
                     /                  
               fib(4)                fib(3)   
             /                      /     
         fib(3)      fib(2)         fib(2)    fib(1)
        /             /           /      
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    
fib(1) fib(0)

Extra space: O(n) if we consider function call stack size. Otherwise O(1)

Method 2: Dynamic Programming – Top Down Approach

We can void the repeated work by storing the numbers calculated so far.

/* the real function to compute the fibonacci numbers */
int _fib(int * st, int n)
{
    /* if the value has not stored yet, computed it */
    if (st[n] == -1) {
        st[n] = _fib(st, n-1) + _fib(st, n-2);
    }

    return st[n];
}

/* a wrapper function */
int fib(int n)
{
    /* array to store the fibonacci numbers */
    int st[n+1];
    int res;
    int i;

    st[0] = 0;
    st[1] = 1;
    for (i=2; i<=n; i++) {
        st[i] = -1;
    }

    _fib(st, n);
    return st[n];
}

Time complexity: O(n)

Extra space: O(n)

Method 3: Dynamic Programming – Bottom Up Approach

Another approach which also store the calculated number so far.

int fib(int n)
{
    int st[n+1];
    int i;
    
    st[0] = 0;
    st[1] = 1;
    
    for (i=2; i<= n; i++)
    {
        st[i] = st[i-1] + st[i-2];
    }
    
    return st[n];
}

Time complexity: O(n)

Extra space: O(n)

Method 4: Dynamic Programming – Space Optimized Method 3

We can optimize the space used in method 3 by storing the previous two numbers only because that are all we need to get the next Fibonacci numbers.

int fib(int n)
{
    int a = 0, b = 1, c;
    int i;
    
    for (i=2; i<=n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Time complexity: O(n)

Extra space: O(1)

Method 5: Using Matrix

This method relies on 2-dimensional system of linear difference equations for Fibonacci sequence. If we n times multiply the matrix M = {{1,1}, {1,0}} to itself (in other word calculate power(M, n)) then we get the (n+1)th Fibonacci number as the element at row and column (0,0) in the resultant matrix.

fibonacci_5

Here is how we do that:

/* Helper functions */
void multiply(int F[2][2], int M[2][2]);
void power1(int F[2][2], int n);

int fib(int n)
{
    /* We don't need to compute the matrix for these values */
    if (n<2)
        return n;
    
    int F[2][2] = {{1,1}, {1,0}};
    
    power(F, n-1);
    return F[0][0];
}

/* multiply 2 matrices F and M of size 2*2 and puts the result back to F */
void multiply(int F[2][2], int M[2][2])
{
    int w = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int x = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int y = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][1];
    
    F[0][0] = w;
    F[0][1] = x;
    F[1][0] = y;
    F[1][1] = z;
}

/* designed for fib only */
void power(int F[2][2], int n)
{
    int i;
    int M[2][2] = {{1,1}, {1,0}};
    
    for (i=2; i<=n; i++)
    {
        multiply(F, M);
    }
}

Time complexity: O(n)

Extra space: O(1)

Method 6: Using Matrix – Optimized Method 5

The method 5 can be optimized to work in O(log n) time complexity. By implementing the Divide and Conquer to power and multiplication, we can do better.

/* Helper functions */
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);

int fib4(int n)
{
    if (n<2)
        return n;
    
    int F[2][2] = {{1,1}, {1,0}};
    
    power(F, n-1);
    return F[0][0];
}

/* multiply 2 matrices F and M of size 2*2 and puts the result back to F */
void multiply(int F[2][2], int M[2][2])
{
    int w = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    int x = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    int y = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][1];
    
    F[0][0] = w;
    F[0][1] = x;
    F[1][0] = y;
    F[1][1] = z;
}

/* designed for fib only, optimized it using Divide and Conquer */
void power(int F[2][2], int n)
{
    if (n==0 || n==1)
        return;
    int M[2][2] = {{1,1}, {1,0}};

    power(F, n/2);
    multiply(F, F);
    if (n%2) {
        multiply(F, M);
    }
}

Time complexity: O(log n)

Extra space: O(log n) if we consider the function call stack size, otherwise O(1)