My Weblog

Blog about programming and math


SPOJ Fibonacci Sum is about adding fibonacci number in given range [n,m]. The Wikipedia article says “The sum of the first n Fibonacci numbers is the (n + 2)nd Fibonacci number minus 1” [second identiy]. Rest is simple.

using namespace std;
typedef unsigned long long ll;
ll  MOD=ll( 1000000007);
ll Fibo(int n)
		ll  fib[2][2]={{1,1},{1,0}},ret[2][2]={{1,0},{0,1}},tmp[2][2]={{0,0},{0,0}};
				memset(tmp,0,sizeof tmp);
				for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) 
				for(int i=0;i<2;i++) for(int j=0;j<2;j++) ret[i][j]=tmp[i][j];
			memset(tmp,0,sizeof tmp);
			for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) 
                        for(int i=0;i<2;i++) for(int j=0;j<2;j++) fib[i][j]=tmp[i][j];

		return (ret[0][1])%MOD;

	int main()
		int t,m,n;

January 9, 2011 - Posted by | Programming


  1. can u please explain the method of this algorithm which u r applying ??
    why changing matrix ret() for odd values of n
    and dividing n by 2???

    Comment by anuarg | January 22, 2011 | Reply

    • Hi Anurag, I have already given the wiki link for algorithm. Do you know how to calculate a^n by repeated squaring. For odd value of n , i have taken a tmp matrix for intermediate calculation and coping back it “ret” because i have to return this value as soon as function return. Look at this wiki page and try to run this fibo function for 3 and you will get idea why we have to copy the tmp value back to ret.

      Comment by tiwari_mukesh | January 23, 2011 | Reply

  2. why we have added MOD in Fibo(m+2)-Fibo(n+1) ??

    Comment by sidharth | December 15, 2012 | Reply

    • In case Fibo(m+2) – Fibo(n+1) become negative which is very much possible.

      Comment by mayankyadav1993 | October 27, 2014 | Reply

Leave a Reply

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

You are commenting using your 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

%d bloggers like this: