title: Nth power Matrix multiplication .Better approach
body: <p>I am having a matrix [2,2][1,0].I need the nth multiflication of this 2*2 matrix.When I use simple multiplication ,I can do in O(n) or O(logn).
  O(logn) code :</p>
  
  <pre><code>int NUM(int n)
   {
    int F[2][2] = {{2,2},{1,0}};
    if(n == 0)
        return 0;
    power(F, n-1);
    return F[0][0];
   }
  
  /* Optimized version of power() */
  void power(int F[2][2], int n)
  {
    if( n == 0 || n == 1)
    return;
    int M[2][2] = {{2,2},{1,0}};
  
   power(F, n/2);
    multiply(F, F);
  
   if( n%2 != 0 )
     multiply(F, M);
  }
  </code></pre>
  
  <p>It works pretty fine with small value of n.But once if n is in order of 10^9 or more.int,long int even long long int won't work.So,I believe this method doesn't seem
  much of help.</p>
  
  <p>Basically my problem is : the numbers get pretty big which doesnt even come in long long int.Then how could I deal with it.</p>
  
  <p>Can anyone suggest me any formula or algorithm to get the nth power of 2*2 matrix[2,2][1,0]when n is of 10^9 ?</p>
  
  <p>Thanks</p>