Fastest way to compute Fibonacci Number

While we all know that matrix exponentiation is asymptotically fastest way to compute N^thFibonacci number, there is a still faster way-

If we know F(k) and F(k+1), then we can find

F(2k) = F(k)[2F(k+1) – F(k)]
F(2k+1) = F(k+1)² + F(k)²

This is fast doubling. Here is my python implementation-

#Fast Fibonnaci

mem = dict()

def fib(n):
    if n <= 2:
        return 1
    if n in mem:
        return mem[n]
    k = n/2
    a = fib(k + 1)
    b = fib(k)
    ans = 0
    if n % 2 == 1:
        ans = a*a + b*b
    else:
        ans = b*(2*a - b)
    mem[n] = ans
    return ans

if __name__ == "__main__":
    n = int(raw_input("Enter n(0 to quit) : "))
    while n:
        print fib(n)
        n = int(raw_input("Enter n(0 to quit) : "))

Note: I have taken the sequence as 1, 1, 2, 3… However some people consider the sequence as 0, 1, 1, 2, 3…

Note 2: For large ‘n’ (~ 10^8), the intermediate values are very large. Hence most of the time is spent in multiplication of such big numbers.