While we all know that matrix exponentiation is asymptotically fastest way to compute NthFibonacci 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)2 + F(k)2
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.