While we all know that matrix exponentiation is asymptotically fastest way to compute N^{th}Fibonacci 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
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…

### Like this:

Like Loading...

*Related*

Hi, good one. Just noted this last comment: “Note: I have taken the sequence as 1, 1, 2, 3… However some people consider the sequence as 0, 1, 1, 2, 3…”

In fact both the sequences are the same (not to mention they are correct). When some people start the sequence at 0, the value of n starts at 0. When others start the sequence at 1, the value of n starts at 1. In fact, in any standard text of reference I have seen, this is the case. That means, both are same. We just need to mention ” n starts at 1″, rather than “the sequence starts at 1″.

This is the paper: http://www.m-hikari.com/imf-password2008/1-4-2008/ulutasIMF1-4-2008.pdf