Take the 2-minute tour ×

what would be the most efficient way to calculate the sum of Fibonacci numbers as: sum between(inclusive of both) F(n) and F(m) where F(n) is the nth Fibonacci number and F(m) is the mth (with F(0)=0;F(1)=1). E.g. if n=0, m=3 the we need to find F(0)+F(1)+F(2)+F(3)=4; Just by brute force it will take long time(as 0=<n<=m<10^9). If it can be done via matrix exponentiation then how?

share|improve this question
I would be very happy to know the application of this answer! –  rjobidon Dec 5 '10 at 3:51
I think we've teased you long enough, in particular with the hint about Binet (instead you should use linear algebra as hinted in your question). Also beware that The F(m+2) - F(n+2) - 2 isn't quite correct but you can figure it out given that the sum of fibo # to n is effectively F(n+2) -1 (hint: you want the sum inclusive of F(n) and hence you need to substract the sum of fibo # up to n-1 and substract this from F(m+2) -2). Anyway... it looking and smelling like HOMEWORK, the SO community shouldn't help too much ;-) –  mjv Dec 5 '10 at 4:50
@mjv - it smells like coding competition problem to me –  Attila Apr 13 '12 at 21:07

3 Answers 3

up vote 8 down vote accepted

F(m+2) - F(n+2) - 2 (discussion)

Literally, the sum of your upper bound m, minus the sum of your lower bound n.

share|improve this answer

Given that "the sum of the first n Fibonacci numbers is the (n + 2)nd Fibonacci number minus 1." (thanks, Wikipedia), you can calculate F(m + 2) - F(n + 2) - 2. Use Binet's Fibonacci number formula to quickly calculate F(m + 2) and F(n + 2). Seems fairly efficient to me.

Update: found an old SO post, "nth fibonacci number in sublinear time", and (due to accuracy as mjv and Jim Lewis have pointed out in the comments), you can't really escape an O(n) solution to calculate F(n).

share|improve this answer
+1, for the additional links and more complete answer. –  MrGomez Dec 5 '10 at 4:02
@MrGomez had to +1 you too for beating me to the basic formula :) –  jball Dec 5 '10 at 4:03
All good on the formula. When it comes to computation, you'll need a mighty precise calculation of Phi and/or sqrt(5) to use Binet on big numbers... –  mjv Dec 5 '10 at 4:07
@mjv, true - I'm not sure how precise they need to be to avoid rounding errors out to F(1 billion)... –  jball Dec 5 '10 at 4:11
@jball: F(10^9) has about 204 million digits, if I've calculated correctly, so you'll probably need to know phi and its large powers to that precision. –  Jim Lewis Dec 5 '10 at 4:24

Algorithm via matrix property explanation found here and here

class Program
    static int FibMatrix(int n, int i, int h, int j, int k)
        int t = 0;

        while (n > 0)
            if (n % 2 == 1)
                t = j * h;
                j = i * h + j * k + t;
                i = i * k + t;
            t = h * h;
            h = 2 * k * h + t;
            k = k * k + t;
            n = n / 2;

        return j;            

    static int FibSum(int n, int m)
        int sum = Program.FibMatrix(n, 1, 1, 0, 0);

        while (n + 1 <= m)
            sum += Program.FibMatrix(n + 1, 1, 1, 0, 0);

        return sum;

    static void Main(string[] args)
        // Output : 4
        Console.WriteLine(Program.FibSum(0, 4).ToString());

share|improve this answer

Your Answer


