Marie Binet loved Fibonacci..

All of us in our lifetime have once stumbled upon the problem of calculating Fibonacci Number. Did you know that about the famous Binet's Formula, with the help of which you can easily calculate nth Fibonacci Number. 

         

So to accurately calculate Fibonacci numbers using Binet's formula, you need an accurate interpretation of √5. Since √5 is irrational, it cannot be accurately represented using double or float, hence Binet's formula doesn't work with these types (however, the rounding in the computation leads to exact results for some small inputs). Since the Fibonacci numbers are integers, you can get exact results from Binet's formula using double or float for more arguments by rounding afterwards,That will return the correct result for almost all n small enough that the result can be exactly represented as a double. These aren't many, however. 

A double typically has only 53 bits of precision, so only Fibonacci numbers smaller than 2⁵³ can be exactly represented as a double (plus a few larger ones divisible by sufficiently high powers of 2). The last Fibonacci number smaller than 2⁵³ is F(77), but F(78) is divisible by 8, so also exactly representable as a double with 53 bits of precision. However, the above produces correct results only for n <= 70 here, from 71 on, the rounding error is too large (incidentally, the result of Binet's formula using doubles is always too large here, so using floor instead of round would produce the correct result also for F(71), but no further).

With the standard datatypes, not many Fibonacci numbers are exactly representable, the last to fit in an (unsigned) 64 bit type is F(93); for 128 bits, the last is F(186). 

Following is the C++ implementation of Binet's formula to find the nth Fibonacci Number

#include<iostream>

#include<cmath>

using namespace std;

double binet(unsigned int n)

{

    static const double phi = (1 + sqrt(5))*0.5;

    double fib = (pow(phi,n) - pow(1-phi,n))/sqrt(5);

    return round(fib);

}

int main(){

    cout<<binet(n);

    return 0;

}

I you want to read more on generating, click the following Fibonacci Number. However, finding large Fibonacci Number does not have any major practical significance.