无符号长整型不会超过第 93 个斐波那契数？

Question

这是我为查找第 n 个斐波那契数而编写的代码：

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;
}

虽然算法运行得很快，但当 n>93 时，输出开始变得异常。我认为/知道这是因为 unsigned long long 的 64 位大小。我是 C++ 新手，但有没有办法解决这个问题，以便我可以获得 fib(9999) 之类的答案？

谢谢

Answer 1

http://gmplib.org/

GMP 是一个用于任意精度算术的免费库，可对有符号整数、有理数和浮点数进行操作。除了运行 GMP 的机器中的可用内存所暗示的精度之外，精度没有实际限制。 GMP有丰富的函数集，并且函数有规范的接口。

GMP的主要目标应用是密码学应用和研究、互联网安全应用、代数系统、计算代数研究等...

Answer 2

使用 bigint 库。网络上有很多（例如，这里和这里）或您自己的。

编辑：自己推出比我预期的要困难得多。算术并不是最难的部分；它以十进制形式打印结果。

Answer 3

上面的答案是正确的，但是通过让 n 为 128，您可以非常接近最大的 64 位数字！

Answer 4

Boost Libraries 是标准化 C++ 的人们去发挥作用的地方。 使用 C++ boost 库有什么优势？ 简而言之，如果你使用 C++ 开发，你应该有 Boost。

Boost 通过 Boost.Multi precision 库方便地提供对多精度算术（或“bignums”）的轻松访问。当前后端的选择是：

• 纯C++代码
• GNU 多精度
• LibTom

如果您不想经历安装 GMP 的痛苦（或处理许可问题），或者只是不想将任何内容与您的应用程序一起打包，那么您可以使用第一个，即 #include -仅有的。这是一个简单的例子，就是这样做的：

#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";
}

要编译它，只需确保 Boost 标头位于包含路径中的某个位置。执行结果程序会产生：

30! = 265252859812191058636308480000000