Unsigned Long Long Won't Go Beyond The 93th Fibonacci Number?

Question

Here's the code I wrote for finding the n-th Fibonacci number:

unsigned long long fib(int n)
{
    unsigned long long u = 1, v = 1, t;

    for(int i=2; i<=n; i++)
    {
        t = u + v;
        u = v;
        v = t;
    }

    return v;
}

While the algorithm runs pretty quickly, the output starts to freak out when n>93. I think/know it's because of the unsigned long long's 64bit size. I'm new to C++ but are there ways of getting around this so I can get the answer of something like fib(9999)?

Thanks

Warlock

Interesting. I was surprised that Fibonacci numbers grew quickly enough that F(94) > ~2^63. – Stoneman

Errr... how can this code work without braces for the for loop? – Anadiplosis

@Everyone Sorry I made some mistakes inputting the code. This is just error in transcribing though. fib(94) still gives me some Frankenstein number... – Warlock

@John Feminella: The Fibonacci sequence grows exponentially. Binet's Formala says F(n) = (phi^n - (-1/phi)^n) / sqrt(5), where phi = (sqrt(5)+1)/2. – Gasp

Fibbonacci[x] behaves very similar to Exp[x/2] – Rickets

@Derek: I'm aware of that, but I'm still surprised! Lots of real-world things that grow exponentially don't get very big quickly. As a simple example, consider compound interest. If you invest $10,000 at 10% annual interest in the stock market, even at t = 94 years you still don't have anywhere close to 2^64 (although you do have ~$80 million). – Stoneman

@John Ferminella, Just to be rigorous, I used unsigned long long so the maximum value goes all the way up to 2^64. Anyway, fib(94)> 2^64. That's some growth! – Warlock

Agreed. fib(94) > 2^64. – Waly

Answer 1

http://gmplib.org/

GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating-point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on. GMP has a rich set of functions, and the functions have a regular interface.

The main target applications for GMP are cryptography applications and research, Internet security applications, algebra systems, computational algebra research, etc...

Yasmineyasu

Answer 2

Use a bigint library. There are plenty around the web (e.g., here and here) or roll your own.

EDIT: Rolling your own is much more difficult than I expected. The arithmetic isn't the hard part; it's printing out the result in decimal form.

Morel

What do you mean "roll" your own? Write my own bigint? – Warlock

@Leebuntu Yes, that's exactly what he means – Chlorinate

@Leebuntu: Yes. For the purpose at hand, you only need operator+, which is pretty easy to code up with respect to a vector<unsigned> representing an arbitrarily large integer. (Of course, you would need operator<< to write out the answer.) – Morel

The last digit is just the number mod 10. Divide by 10 and repeat for the next-last number, and so on. But using gmp is a much better idea than rolling your own! – Irritability

@PaulCrowley: At the time, I was probably wondering if there was a way to avoid division and print left to right in O(n) time (n = digits). – Morel

Answer 3

Boost Libraries is where the people who standardize C++ go to play. What are the advantages of using the C++ boost libraries? In short, if you develop with C++, you should have Boost.

Boost, conveniently, provides easy access to multiprecision arithmetic (or “bignums”) with the Boost.Multiprecision library. Current choices of backend are:

• pure C++ code
• GNU Multiprecision
• LibTom

If you do not want to go through the grief of installing GMP (or deal with the licensing issues), or just don’t want to package anything alongside your application at all, then you can use the first one, which is #include-only. Here is a simple example that does just that:

#include <iostream>

#include <boost/multiprecision/cpp_int.hpp>
using integer = boost::multiprecision::cpp_int;

integer factorial( unsigned n )
{
  integer result = 1;
  while (n > 1)
  {
    result *= n;
    n      -= 1;
  }
  return result;
}

int main()
{
  std::cout << "30! = " << factorial( 30 ) << "\n";
}

To compile that just make sure that the Boost headers are somewhere in your include path. Executing the resulting program produces:

30! = 265252859812191058636308480000000

Damnify