## nth Fibonacci Number

February 15, 2010 Leave a comment

I was in the test run of a programming contest just a couple of days back and there was this good old problem of finding out the nth Fibonacci Number. But the constraints were tight (upto 10^9) and the number of test cases were also high ( ~100). Well I knew that the conventional DP solution of O(n) won’t work, still I tried and got the TLE :P. Out of the shackles of laziness, I went out to code the O(log(n)) version of calculating the nth Fibonacci Number. The method to do it is very simple, the recurrence is

I used recursion and coded it. Interestingly, I got TLE again ๐ฆ . When I ran the code on my system it was very slow for high values. Any Guesses why ??? ๐ Think it over ๐

Anyways, I figured out immediately why it was slow and then used the good old technique of Memoization to code the same solution with slight modification. This time it got accepted ๐

**The code which I made.**

#include<stdio.h> #include<string.h> typedef long long LL; int mem[5000000]; LL fib(LL n) { if ( n == 1 ) return 1; if ( n == 2 ) return 1; if (n & 1 ) // odd { LL t1, t2, t3; if ((n+1)/2 < 5000000 && mem[(n+1)/2] != 0 ) t1 = mem[(n+1)/2]; else { t1 = fib( (n + 1)/2)%10007; if ( (n+1)/2 < 5000000) mem[(n+1)/2] = (int)t1; } if ((n+1)/2 - 1 < 5000000 && mem[(n+1)/2-1] != 0 ) t2 = mem[(n+1)/2-1]; else { t2 = fib( (n + 1)/2-1)%10007; if ( (n+1)/2 -1 < 5000000) mem[(n+1)/2-1] = (int)t2; } return ((t1*t1)%10007 + (t2*t2)%10007)%10007; } else { LL t1, t2, t3; if ((n)/2 < 5000000 && mem[(n)/2] != 0 ) t1 = mem[(n)/2]; else { t1 = fib( (n )/2)%10007; if ( (n)/2 < 5000000) mem[(n)/2] = (int)t1; } if ((n)/2 - 1 < 5000000 && mem[(n)/2-1] != 0 ) t2 = mem[(n)/2-1]; else { t2 = fib( (n)/2-1)%10007; if ( (n)/2 -1 < 5000000) mem[(n)/2-1] = (int)t2; } if ((n)/2 + 1 < 5000000 && mem[(n)/2+1] != 0 ) t3 = mem[(n)/2+1]; else { t3 = fib( (n)/2+1)%10007; if ( (n)/2 +1 < 5000000) mem[(n)/2+1] = (int)t3; } return (((t2 + t3)%10007)*t1)%10007; } } int main() { int t; memset((void *)mem,0,5000000*sizeof(int)); long long int n; scanf("%d",&t); while (t--) { scanf("%lld",&n); if ( n == 1) { printf("1\n"); continue;} if ( n == 2) { printf("2\n"); continue;} printf("%lld\n",fib(n+1)); } return 0; }

It was good that I coded it, because nowadays people are not satisfied with the good old O(n) DP method :P. They want the O(log(n)) code. I remember a company at our campus asked a guy to do it, the interviewer helped him a lot but he couldn’t answer it. Nice practice to do actually ๐

## Recent Activity