Fibonacci sum problem

[ankur12106037]

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

#include<iostream>
#include<math.h>
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<<sum<<"\n";
   }
return 0;
}
long int power_multiply(long int a,long int &b)
{
    double x=(1+sqrt(5))/2,ans=1,y=x;
    while(a>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;
}

[helios]

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

double round(double x){
    return floor(x + 0.5);
}

That should be easier on the CPU pipeline.

[ankur12106037]

@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.

[helios]

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

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

[ankur12106037]

thanks @helios this generalisation for sum to n number did help me and i got my solution accepted on spoj :)