«

»

Jul 20

Calculating Fibonacci Numbers

The following C++ code calculates the Nth number in the Fibonacci sequence.  The first routine recursively calculates F_n, however it is very inefficient and takes an unrealistic amount of time to calculate even moderately high values for F_n (say 100).  The second routine generates the sequence sequentially on the fly up to F_n, and is a much quicker algorithm (orders of magnitude for high values).

#include <iostream>
#include <vector>

int calcFibSlow(const int& n)
{
    if (n <= 1)
        return n;
    else
        // Recursively calculate F_n
        return (calcFibSlow(n-1) + calcFibSlow(n-2));
}

int calcFibFast(const int& n)
{
    // Create a vector of integers, n+1 because wants zeroth F_n
    std::vector<int> listN(n+1,0);
    listN[1] = 1;

    // Generate up to F_n
    for (int ii = 2; ii <= n; ++ii)
    {
        listN[ii] = listN[ii-1] + listN[ii-2];
    }

    return listN[n];

}

int main()
{
    int nVal;
    // Read in the desired F_n
    std::cin >> nVal;
    std::cin.ignore();
    // Output the values of both routines
    std::cout << calcFibSlow(nVal) << std::endl;
    std::cout << calcFibFast(nVal) << std::endl;
    std::cin.get();
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>