Finding the sum of Fibonacci Numbers

What would be the most efficient way to calculate the sum of Fibonacci numbers from F(n) to F(m) where F(n) and F(m) are nth and mth Fibonacci numbers respectively and 0 =< n <= m <109 (with F(0)=0, F(1)=1).

For example, if n=0, m=3, we need to find F(0)+F(1)+F(2)+F(3).

Just by brute force it will take long time for the range of n and m mentioned. If it can be done via matrix exponentiation then how?

7
задан Sнаđошƒаӽ 2 December 2016 в 11:15
поделиться