Here's O(log n) solution [1]:

  def fib_sicp(n):
      a, b, p, q = 1, 0, 0, 1
      while n > 0:
          if n % 2 == 0: # even
              oldp = p
              p = p*p + q*q
              q = 2*oldp*q + q*q
              n //= 2
          else:
              olda = a
              a = b*q + a*q + a*p
              b = b*p + olda*q
              n -= 1
      return b
  

[1]: http://stackoverflow.com/questions/1525521/nth-fibonacci-num...

It is ~20 times faster for n=10000