Fibonacci number (idea)

Most algorithms I have seen that calculate the n:th fibonacci number do so in O(n) time. There is however a way to do it in O(lg n) time. The algorithm makes use of the fact that it is possible to calculate 'i to the power of n' in O(lg n) time this way:

int Pow(i, n)
{
  if (n == 0)
    return 1;
  else
  {
    int r = Pow(i, n / 2);  // assumes integer division
    r = r * r;
    if (n % 2 == 1)         // if n is odd we need to multiply
      r = r * i;            // r with i to get the correct result
    return r;
  }
}

The formula below shows that the powers of a certain 2x2 matrix results in another 2x2 matrix containing some usefull fibonacci numbers:

[0 1]^n    [fib(n - 2) fib(n - 1)]
[1 1]   =  [fib(n - 1) fib(n)    ]

The pseudo code below shows the full algorithm:

int Fib(int n)
{
  Matrix F = {{0, 1}, {1, 1}};
  F = Pow(F, n);
  return F[1][1]; // row 2, column 2
}

Matrix Pow(Matrix M, int n)
{
  if (n == 0)
    return {{1, 0}, {0, 1}}; // the identity matrix
  else
  {
    Matrix R = Pow(M, n / 2);
    R = R * R;
    if (n % 2 == 1)
      R = R * {{0, 1}, {1, 1}};
    return R;
  }
}