fib.hs

fib' 1 = (0, 1, 1)
fib' n = let (a, b, c) = fib' (n `div` 2)
             a' = a*a + b*b
             b' = a*b + b*c
             c' = b*b + c*c
         in  if n `rem` 2 == 1 then (b', c', b' + c')
                               else (a', b', c')

fib 0 = 0
fib n = let (_, v, _) = fib' n in v

fib.py

def fib(n, memo={1: (0, 1, 1)}):
    if n in memo:
        return memo[n]
    a, b, c = fib(n/2)
    a, b, c = a*a+b*b, a*b+b*c, b*b+c*c
    if n & 1:
        a, b, c = b, c, b+c
    memo[n] = a, b, c
    return memo[n]

fib2.py

def fib(n, memo={0: (0, 1)}):
    if n not in memo:
        a, b = fib(n // 2)
        c = a * (2 * b - a)
        d = a * a + b * b
        memo[n] = (d, c + d) if n & 1 else (c, d)
    return memo[n]