Need help in FIBNC

CodeChef-DSA-learners
,
1

When I am using the formula for calculating the fibonacci number, I am getting WA but with Matrix exponentiation I got right answer.
Can anyone explain why?

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007

ll fib(ll n) {
double phi = (1 + sqrt(5)) / 2;
return round(pow(phi, n) / sqrt(5));
}

int main()
{
ll t;
cin>>t;

while(t--)
{
    ll n,k;
    cin>>n>>k;
    
    ll x=n/k, y=n%k, ans=0;
    x%=mod;
    
    if(x>0)
    {
        ans+=(x*(fib(k+1)-1))%mod;
        ans%=mod;
    }
    if(y>0)
    {
        ans+=((fib(y+1)-1))%mod;
        ans%=mod;
    }
    
    cout<<ans<<endl;
    
    
    
    
}

}

2

Floating point calculations are very inaccurate for such large powers, and pow(phi, n) can become very large very quickly. You would overflow before reaching the 100th fibonacci number.

3

Thanks a lot … :slight_smile: