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.