# Tag Archive : algorithm

/ algorithm

### Fibonacci Numbers in C\C++

December 11, 2015 | Article | No Comments

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

or:

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

with seed values

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.

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)

Social media & sharing icons powered by UltimatelySocial