0

I am generating the sequence 1,3,8,22,60,....
upto 10^9 the term mod of 10^9+7;
However my code is giving inaccurate answers for large value of n.
The formula I am using is ((1+Q)^(n+1)-(1-Q)^(n+1))/(4*Q)
Here Q is sqrt (3)
Here is my code.Can someone point out the error in the code or any ways to remove this problem.
Any help will be highly appreciated.

#include <iostream>
#include<stdio.h>
#define big long long int
#define foo(b) static_cast<big>(b)
big ro(long double x)
{
    if(x-(big)x>=0.5)
    {
        return x+1;
    }
    else
    return x;
}
big m=1000000007;
long double Q=1.7320508075688772935274463415058723669428052538103806;

using namespace std;
long double mod(long double a,big b)
{
big result = static_cast<big>( a / b );
return a - static_cast<long double>( result ) * b;
}
long double modex(long double a,big b, big n){
    long double r = 1;
    while (1){
        if (b&1)
            r = mod(mod(mod(r,m),m) * a,m) ;
        b /= 2;
        if (!b )
            break;
        a = mod(mod(a,m) *mod( a,m),  m);
    }
    return r;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","w",stdout);
cout<<10000<<endl;
for(big i=1;i<=10000;i++)
//cout<<1000000000<<endl;

cout<<i<<endl;
freopen("out.txt","w",stdout);
freopen("in.txt","r",stdin);
#endif
big t,n;
cin>>t;
while(t--)
{cin>>n;
long double ans1= (modex((1.00000000000 + Q),(1+n),m));
long double ans2 = (modex((1.0000000000 - Q),(1+n),m )) ;
long double ans3=(1/ (4*Q));
long double ans=(ans1-ans2);
//ans=ans/ans3;
cout<< ro(ans*ans3)<<endl;
//cout<<ans<<endl;
}
    return 0;
}
2
Contributors
1
Reply
2
Views
5 Years
Discussion Span
Last Post by Ancient Dragon
0

There is no solution using standard C/C++ variables such as long double because they have a finite limit before overflow occurs. Check your compiler's limits.h header file to find out what your compiler supports. If you need that large of numbers then I'd suggest using one of the huge number libraries such as one of these.

Also check limits.h to see if your compiler supports long long and long double, some compilers support the names but their sizes are the same as long and double.

Edited by Ancient Dragon

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.