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

发布于 2024-09-06 19:32:12 字数 378 浏览 5 评论 0 原文

下面是我为查找第 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) 之类的答案？

谢谢

原文

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

面犯桃花 2024-09-13 19:32:12

http://gmplib.org/

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

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

回复收藏 0 原文

不必在意 2024-09-13 19:32:12

使用 bigint 库。网络上有很多（例如，此处和此处）或自行推出。

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

回复收藏 0 原文

星光不落少年眉 2024-09-13 19:32:12

Boost Libraries 是 C++ 标准化人员的工作场所。使用 C++ boost 库有哪些优点？< /a> 简而言之，如果你用C++开发，你应该有Boost。

Boost 通过 Boost.Multi precision 库。当前后端的选择是：

纯 C++ 代码
GNU Multi precision
LibTom

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

#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

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: