• Source 
    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. }