### Fibonacci sum problem

 Question->http://www.spoj.com/problems/FIBOSUM/ Basically question is to find the sum of fibonacci numbers starting from N to M I did this question using the factor (1+sqrt(5))/2.I found N,N+1 using this factor by O(log N) multiplication.Then finally i traversed all the numbers from N+2 to M and side by side adding their sum.My code takes O(N-M+logN) time.But i am getting time limit exceeded on this solution.What can i do to improve the time complexity of my solution.I thought of doing using dynamic programming will it be faster ??plz help

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445`` ``````#include #include long int power_multiply(long int,long int&); using namespace std; int main() { long int N,M,a,b,sum=0,c,t; cin>>t; while(t--){ cin>>N>>M; a=power_multiply(N,b); sum=a+b; long int i=N+2; while(i!=M+1) { c=b+a; sum=sum+c; sum%=1000000007; a=b; b=c; i++; } cout<0) { if(a%2!=0) { ans=ans*x; } x=x*x; a=a/2; } if(ceil(ans/sqrt(5))-ans/sqrt(5)>=0.5){a=floor(ans/sqrt(5));} else{a=ceil(ans/sqrt(5));} if(ceil((ans*y)/sqrt(5))-(ans*y)/sqrt(5)>=0.5){b=floor((ans*y)/sqrt(5));} else{b=ceil((ans*y)/sqrt(5));} return a; }``````
Last edited on
Well, here's something easy: Let p be the number of bits of a turned on, then the value of ans at line 39 is x(p*p+p)/2.

For rounding, you can use
 ``123`` ``````double round(double x){ return floor(x + 0.5); }``````
That should be easier on the CPU pipeline.
Last edited on
@helios I improved my code for finding the nearest integer by following the rounding method u told.But still my code is exceeding the time limit.
A constant time algorithm could use the fact that
Let G(n) = sum of F(i) for i = 0 to n, then
G(0) = 0
G(1) = 1
G(2) = 2
G(n) = F(n + 2) - 1

 ``123456789`` ``````0 0 0 1 1 1 2 1 2 3 2 4 4 3 7 5 5 12 6 8 20 7 13 33 8 21 54``````
thanks @helios this generalisation for sum to n number did help me and i got my solution accepted on spoj :)
Topic archived. No new replies allowed.