title: Matrix Exponentiation Algorithm for large values of N
body: <p>I want to calculate the Fibonacci of very large value of N ie. 10^6 with a complexity of O(logN).
  Here is my code but it gives the result for 10^6 in 30 seconds which is very time consuming.Help me point out the mistake.I have to give the output in modulo 10^9+7.</p>
  
  <pre><code>static BigInteger mod=new BigInteger("1000000007");
  
  BigInteger fibo(long n){
      BigInteger F[][] = {{BigInteger.ONE,BigInteger.ONE},{BigInteger.ONE,BigInteger.ZERO}};
      if(n == 0)
          return BigInteger.ZERO;
      power(F, n-1);
      return F[0][0].mod(mod);
  }
  
  void power(BigInteger F[][], long n) {
      if( n == 0 || n == 1)
          return;
      BigInteger M[][] = {{BigInteger.ONE,BigInteger.ONE},{BigInteger.ONE,BigInteger.ZERO}};
      power(F, n/2);
      multiply(F, F);
      if( n%2 != 0 )
          multiply(F, M);
    }
  
  void multiply(BigInteger F[][], BigInteger M[][]){
      BigInteger x =  (F[0][0].multiply(M[0][0])).add(F[0][1].multiply(M[1][0])) ;
      BigInteger y =  F[0][0].multiply(M[0][1]).add(F[0][1].multiply(M[1][1])) ;
      BigInteger z =  F[1][0].multiply(M[0][0]).add( F[1][1].multiply(M[1][0]));
      BigInteger w =  F[1][0].multiply(M[0][1]).add(F[1][1].multiply(M[1][1]));
  
      F[0][0] = x;
      F[0][1] = y;
      F[1][0] = z;
      F[1][1] = w;
  }
  </code></pre>