[ChristianMarks]

The O(log N) algorithm, in Python:

  def fib(n):
    a,b,x,y = 0,1,0,1
    while n != 0:
      if n % 2 == 0:
        a,b = a * a + b * b, 2 * a * b + b * b
        n = n // 2
      else:
        x,y = a * x + b * y, b * x + a * y + b * y
        n -= 1
    return x