Implement the Fibonacci numbers, which are defined as

$F_n={\begin{cases}0&{\mbox{if }}n=0\\1&{\mbox{if }}n=1\\F_{n - 1} + F_{n - 2}&{\mbox{if }}n\geq 2\\F_{n + 2} - F_{n + 1}&{\mbox{if }}n \leq -1\end{cases}}$.

Your function declaration should be

long fibonacci( long n );

The one difficulty is there exists both positive and negative $n$ such that $|F_n| \geq 2^{63}$, so you must determine these value of $n$, and if the user passes a value of $n$ such that $F_n$ cannot be stored in a variable of type long, you must throw a std::range_error exception.

You will use one of three implementations:

You can use the recursive definition, whereby you return either $0$, $1$ or the appropriate formula in terms of other Fibonacci numbers.

You can use an iterative formula where you use two local variables to store the two most previous values, and use those two to calculate the next, then updating the two local variables with the two most recently calculated Fibonacci numbers.

Use std::sqrt and std::pow to calculate

$F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}}$

and then use std::round to round this to the closest integer, after which you will cast the result to long assuming it is not greater than the value a long can hold. At which point does this give an inaccurate answer? Can you guess or explain why?

Test

Try the following program:

#include <iostream>
#include <stdexcept>

unsigned long fibonacci( unsigned long n );
int main();

int main() {
    for ( long n{-100}; n < 100; ++n ) {
        try {
            std::cout << "F( " << n << " ) = "
                      << F( n ) << std::endl;
        } catch ( std::range_error &e ) {
            std::cout << "F( " << n << " ) < 2^63 or "
                      << "F( " << n << " ) >= 2^63."
                      << std::endl;
        }
    }

    return 0;
}