Fast Doubling method to find nth Fibonacci number

One among very common questions asked in maths category in competitive programming is Fibonacci Series.

For a question that asks to find nth term of Fibonacci series, a naive approach to solve is an iterative method like

#define MOD 1000000007
long long int fib(long long int n)
{
    if(n < 2)
        return n;
    long long int a = 0,b = 1,ans;
    int i = 1;
    while(i < n)
    {
        ans = (a+b) % MOD;
        a = b;
        b = ans;
        i++;
    }
    return ans;
}

Above function has an O(n) complexity. With all our patience we may use it to calculate for at most n = 10^9 which gives output in around 10-15 seconds.

But as n gets larger, it takes hours,days,months,years,decades and so on for increasing n.

So the question is can we optimise it? Do we have methods to find nth Fibonacci number in less than a second?

Yes. We have few methods to do this. Out of them matrix exponentiation is most commonly used concept. Another well known concept is fast doubling method, which we are going to learn now.

Fast doubling is based on two formulae

F(2n) = F(n)[2*F(n+1) – F(n)]
F(2n + 1) = F(n)2 + F(n+1)2

Let us consider n starts from 0 and F(0) = 0. So our Fibonacci series would be F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8 …

For calculating terms, F(2n) & F(2n + 1), lets have a record of F(n) & F(n+1). By following this statement and taking care of equations and data type overflow, code would be as follows,

#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007;
long long int a,b,c,d;

void fast_fib(long long int n,long long int ans[])
{
    if(n == 0)
    {
        ans[0] = 0;
        ans[1] = 1;
        return;
    }
    fast_fib((n/2),ans);
    a = ans[0];             /* F(n) */
    b = ans[1];             /* F(n+1) */
    c = 2*b - a;
    if(c < 0)
        c += MOD;
    c = (a * c) % MOD;      /* F(2n) */
    d = (a*a + b*b) % MOD;  /* F(2n + 1) */
    if(n%2 == 0)
    {
        ans[0] = c;
        ans[1] = d;
    }
    else
    {
        ans[0] = d;
        ans[1] = c+d;
    }
}

int main()
{
    long long int n;        /* nth value to be found */
    scanf("%lld",&n);
    long long int ans[2]={0};
    fast_fib(n,ans);
    printf("%lld\n",ans[0]);
    return 0;
}

This code has a complexity of O(log n) which is way too faster than previously discussed function.

Advertisements

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