Fibonacci Numbers

Fibonacci numbers are a sequence of numbers, starting with the numbers 0 and 1, where each successive number is the sum of the previous two. The first few Fibonacci numbers are:

0 1 1 2 3 5 8 13 21 34 55 89 144...

You might be curious what the first Fibonacci number is that's too big to calculate using the standard C++ unsigned long type. A brute-force method of calculating this would be problematic, since it might not be possible to tell when it overflows. But with the XInt library, it's child's play:

#include <iostream>
#include <boost/xint/integer.hpp>

int main() {
    using namespace boost::xint;
    using std::cout;
    using std::endl;

    // Select the limit, in this case the largest number that will fit into an
    // unsigned long.
    integer limit=(std::numeric_limits<unsigned long>::max)();

    // Set the first two numbers in the sequence.
    integer n, n1=0, n2=1;

    // Now count the items in the sequence as we iterate over them, until we
    // come to the first one greater than the limit we've set.
    size_t counter=0;
    cout << counter++ << ": " << n1 << endl;
    cout << counter++ << ": " << n2 << endl;

    while (1) {
        n = n1 + n2;
        if (n > limit) break;

        // That one didn't do it, go back for another try.
        cout << counter++ << ": " << n << endl;

        n1=n2;
        n2=n;
    }

    cout << "The answer is " << counter << " (" << n << ")." << endl;
}

If you're not intimately familiar with the Fibonacci sequence, and how fast the numbers in it grow, the answer might shock you.

As you can see, using the XInt library is just like using the native integer types -- except that an xint::integer won't overflow on you until you completely exhaust your system's memory. :-)