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?