Fastest way to compute Fibonacci Number

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
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
This entry was posted in Programming and tagged . Bookmark the permalink.

One Response to Fastest way to compute Fibonacci Number

  1. Tijo Jose says:

    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″.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s