Fast Fibonacci

Fast_Fibonacci.py

def bits(n):
  '''Represent an integer as an array of binary digits.'''
  bits = []
  while n > 0:
    n, bit = divmod(n, 2)
    bits.append(bit)
  bits.reverse()
  return bits

def fib_fast(n):
  ''' Fast Fibonacci '''

  assert n >= 0
  a, b, c = 1, 0, 1
  for bit in bits(n):
    if bit: a, b = (a+c)*b, b*b + c*c
    else:   a, b = a*a + b*b, (a+c)*b
    c = a + b
  return b