• Source 
    1. #include <stdio.h>
    2.  
    3. void multiply(int F[2][2], int M[2][2]);
    4.  
    5. void power(int F[2][2], int n);
    6.  
    7. /* function that returns nth Fibonacci number */
    8. int fib(int n)
    9. {
    10.   int F[2][2] = {{1,1},{1,0}};
    11.   if (n == 0)
    12.     return 0;
    13.   power(F, n-1);
    14.   return F[0][0];
    15. }
    16.  
    17. /* Optimized version of power() in method 4 */
    18. void power(int F[2][2], int n)
    19. {
    20.   if( n == 0 || n == 1)
    21.       return;
    22.   int M[2][2] = {{1,1},{1,0}};
    23.  
    24.   power(F, n/2);
    25.   multiply(F, F);
    26.  
    27.   if (n%2 != 0)
    28.      multiply(F, M);
    29. }
    30.  
    31. void multiply(int F[2][2], int M[2][2])
    32. {
    33.   int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
    34.   int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
    35.   int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
    36.   int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];
    37.  
    38.   F[0][0] = x;
    39.   F[0][1] = y;
    40.   F[1][0] = z;
    41.   F[1][1] = w;
    42. }
    43.  
    44. /* Driver program to test above function */
    45. int main()
    46. {
    47.   int n = 9;
    48.   printf("%d", fib(9));
    49.   getchar();
    50.   return 0;
    51. }