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
def fib(n):
    if n <= 2:
        return 1
    k = n/2
    a = fib(k + 1)
    b = fib(k)
    if n % 2 == 1:
        return a*a + b*b
    else:
        return b*(2*a - b)

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…

About these ads