开发者

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

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 beca开发者_如何转开发use 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


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...


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜