Just to expand this for people who aren't familiar with this idea, which has a nice analogue with complex numbers, one can take the number a + b sqrt(5) and represent it as the matrix:

    [a, 5b]
    [b,  a]

This implements the multiplication rule for such numbers as a matrix multiplication. There is a straightforward generalization where you replace 5 with -1 and get complex numbers, which is one of the easiest ways to see that the complex numbers are scaled rotation matrices -- which is the easy way to see that a holomorphic function preserves angles and obeys the Cauchy Riemann equation ∂f/∂y = i ∂f/∂x.

It's very cute mathematics, but it's still not O(1). At the very least, exponentiating to the n requires log(n) matrix multiplications.

I'm late to the party, but a quick and dirty implementation of this in ghci computes the 10,000,000th Fibonacci number for me in about 3 seconds, though it takes a lot longer to print to my terminal. It's pretty neat.

   newtype T = T (Rational,Rational) deriving Show
   :{
   instance Num T where { T (a,b) + T (c,d) = T (a+c,b+d);
                          T (a,b) * T (c,d) = T (a*c+5*b*d,b*c+a*d);
                          abs (T (a,b)) = T (a*a+5*b*b,0);
                          fromInteger n = T(fromInteger n,0);
                          signum (T (a,_)) = T (signum a,0);
                          negate (T(a,b)) = T(-a,-b) }
   instance Fractional T where { recip (T(a,b)) = T(a/(a^2-5*b^2),-b/(a^2-5*b^2));
                                 fromRational r = T(r,0)}
   :}
   let r5 = T(0,1)
   let phi = (1+r5)/2
   let psi = (1-r5)/2
   let fromT (T(a,b)) = (a,b)
   let fib n = floor . fst . fromT $ (phi^n-psi^n)/r5
   let x = fib 10000000
   x == 0