views:

158

answers:

2

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

+13  A: 

http://gmplib.org/

BlueRaja - Danny Pflughoeft
Damnit. 2 seconds too slow.
Jamie Wong
Thanks for the fast and concise answer!
Leebuntu
+4  A: 

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.

Marcelo Cantos
What do you mean "roll" your own? Write my own bigint?
Leebuntu
@Leebuntu Yes, that's exactly what he means
Jamie Wong
@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.)
Marcelo Cantos
@Marcello - a bigint that used base10 internally would simplify printing ...
Stephen C