Program for Fibonacci numbers

Program for Fibonacci numbers

The Fibonacci numbers are the numbers in the following integer sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

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

    Fn = Fn-1 + Fn-2

with seed values

   F0 = 0 and F1 = 1.

Method 1 ( Use recursion ):-

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.

Method 2 ( Use Dynamic Programming )

1. int fib(int n)
2. {
3. /* Declare an array to store Fibonacci numbers. */
4. int f[n+1];
5. int i;
6.  
7. /* 0th and 1st number of the series are 0 and 1*/
8. f[0] = 0;
9. f[1] = 1;
10.  
11. for (i = 2; i <= n; i++)
12. {
13. /* Add the previous 2 numbers in the series
14.   and store it */
15. f[i] = f[i-1] + f[i-2];
16. }
17.  
18. return f[n];
19. }

Time Complexity: O(n)
Extra Space: O(n)

Method 3 ( Space Optimized Method 2 )

int fib(int n){

  int a = 0, b = 1, c, i;

  if( n == 0)

    return a;

  for (i = 2; i <= n; i++){

     c = a + b;

     a = b;

     b = c;

  }

  return b;

}

Time Complexity: O(n) Extra Space: O(1)

Method 4 ( Using power of the matrix {{1,1},{1,0}} )

This another O(n) which relies on the fact that if we n times multiply the matrix M = {{1,1},{1,0}} to itself (in other words 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.

The matrix representation gives the following closed expression for the Fibonacci numbers:

1. #include <stdio.h>
2.  
3. /* Helper function that multiplies 2 matrices F and M of size 2*2, and
4.   puts the multiplication result back to F[][] */
5. void multiply(int F[2][2], int M[2][2]);
6.  
7. /* Helper function that calculates F[][] raise to the power n and puts the
8.   result in F[][]
9.   Note that this function is designed only for fib() and won't work as general
10.   power function */
11. void power(int F[2][2], int n);
12.  
13. int fib(int n)
14. {
15. int F[2][2] = {{1,1},{1,0}};
16. if (n == 0)
17. return 0;
18. power(F, n-1);
19.  
20. return F[0][0];
21. }
22.  
23. void multiply(int F[2][2], int M[2][2])
24. {
25. int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
26. int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
27. int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
28. int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
29.  
30. F[0][0] = x;
31. F[0][1] = y;
32. F[1][0] = z;
33. F[1][1] = w;
34. }
35.  
36. void power(int F[2][2], int n)
37. {
38. int i;
39. int M[2][2] = {{1,1},{1,0}};
40.  
41. // n - 1 times multiply the matrix to {{1,0},{0,1}}
42. for (i = 2; i <= n; i++)
43. multiply(F, M);
44. }
45.  
46. /* Driver program to test above function */
47. int main()
48. {
49. int n = 9;
50. printf("%d", fib(n));
51. getchar();
52. return 0;
53. }

Time Complexity: O(n)
Extra Space: O(1)