使用 C++ 查找第 1500000 个 Fib 数

Question

我编写了以下代码来查找第 1500000 个斐波那契数（请忽略可怕的缩进，我大约用了 2 分钟写了这个）。我需要它作为字符串。假设这应该有效：

#include <cstdlib>
#include <iostream>
#include <sstream>
int i;
int b=1;
int c=2;
using namespace std;

int main(int argc, char *argv[])
{

    int fib=1500000;

for (i=1;i<fib-3;i++){
c=b+c;
b=c-b;
}
   stringstream ss;
   ss << c;
   string d=ss.str();
cout << d << endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

它会经历这个过程 1500000-3 次（每次都会超过 3 个数字） 我知道问题在于这个数字太大而无法作为 int 包含。有什么方法可以让我存储它而不将其包含为 int 或文件（因为这会非常低效）？如果是这样，我该怎么做？

Answer 1

使用Bignum 库。

Answer 2

如果您需要精确的形式，您可以使用 bignum 库的其他递归关系之一：

fib(2*n) = fib(n)^2 + fib(n-1)^2
fib(2*n-1) = fib(n)*(2*fib(n-1)+fib(n))

这应该减少 O(log(n)) 而不是 O(n) 所需的计算数量
您可以在此处查看基于此的方法的伪代码：nth fibonacci number in次线性时间

请注意，第 n^ 个斐波那契数需要大约 n*log(phi)/log(2) = n*0.69 个二进制数字来表示，因此精确表示第 1.5M^ 个斐波那契数需要大约 130kb 来表示以二进制表示，或 300kb 作为字符串（大约为 2^(10000000) 或 10^(300000) ）

---

作为双打溢出在大约 n=1500 处删除

您可以直接使用双打来执行此操作，如下所示（改编自 http://en.wikipedia.org/wiki/Fibonacci_number ) ：

double fib( int n )
{
   static const SQRT_5 = sqrt(5.0);
   static const phi = (1.0+SQRT_5)/2.0;
   return floor( (pow(phi,n)/SQRT_5) + 0.5 );
}

尽管如果您需要每个数字，这将不起作用。 （它只会给出第 78 个斐波那契数列之前的每个数字）

Answer 3

Boost 使使用 bignum 变得异常简单。

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

integer fibonacci( unsigned long long n )
{
  integer a = 0;
  integer b = 1;
  while (n --> 0)
  {
    integer c = a + b;
    a = b;
    b = c;
  }
  return a;
}


#include <iostream>
#include <string>

int main( int argc, char ** argv )
try
{
  long long n = std::stoll( argc == 2 ? argv[1] : "" );
  if (n < 0) throw 1;
  std::cout << fibonacci( n ) << "\n";
}
catch (...)
{
  std::cerr << 
    "usage:                                     \n"
    "  fibonacci N                              \n"
    "where N is the Fibonacci number to compute.\n";
  return 1;
}

在上面的示例中，我使用了本机 Boost bignum 类型，即：

• 仅标头（无需编译 Boost！）
• 非常快
  - 我在我的 ancient< 上大约两分钟内计算出了 fibonacci(1500000) /em> AMD Sempron 130。如果我敲掉一个零，结果几乎是瞬时的。

如果这对您来说还不够快， Boost Multi precision 还提供后端：

• GNU GMP
  这是最好的 bignum 库，使用过几乎在所有严重的 bignum 计算环境，但它受到 Copyleft 的阻碍，并且众所周知很难正确设置。
• libTomMath
  这明显更容易安装，但您仍然必须知道自己在做什么。

Answer 4

第 1500000 个斐波那契数列使用此 答案 在 C99 中打印，只需进行更改：

#define BUFFER_SIZE 18935

没有库，输出应类似于（313,482 位）：

129089216811873951612785 ... 853738956168354898000000
took 59s

计算 f(1500000) 30 秒和基本转换，所以大约一分钟。

和：1963年，Stephen P. Geller使用IBM 1620计算机显示最后四位数字每15,000次重复一次，最后五位每150,000次重复一次，最后，在计算机运行后近三个小时，重复最后六位数字 出现在第 1,500,000 个斐波那契数处。

尝试 f(15000) 在线 - 谢谢。

Answer 5

您确定C++ 速度很快吗？

    gawk  -v _____='1500000' -v PREC=20000 -p- -Mbe '

    BEGIN {
     1      _ += ___ = _ ^= ____ = __ = _ < _
     1      _____ += ___
     1      ____ = --_____
     1      do {
     1          print __ = length(_ = fib(____)), substr(_, 1, 50), substr(_, __ + 1 - 50)
        } while (++____ < _____)
    }

     1  function fib(______, _, __, ___, ____, _____)
    {
     1      if ((______ = +_ < ______ ? +______ : +_) < (__ *= (__ = _ ~ _) + (++__))) {
            return (______ - ((! _) < (______ % --__)))
        }
     1      _____ = (___ = __ = (_ = _ < _) ~ _) + ___
    20      while ((___ += ___) <= ______) {
    20          ++____
        }
    21      do {
    21          __ = (__ * __ + _ * _) substr(_ *= __ + __ - _, ___, ! ___)
    21          if (int(______ / (___ /= _____)) % _____) { # 10
    10              __ = (__ + _) substr(_ = __, ___, ! ___)
            }
        } while (____--)
     1      return _
    }
( gawk -v _____='1500000' -v PREC=20000 -p- -Mbe ; )  0.10s user 0.01s system 95% cpu 0.115 total

 313482 12908921681187395161278531776694736120150441703840        
        02113051432895630172796932853738956168354898000000

*C++ 到底是如何花费 59.0 秒来实现 awk 花费 0.115 秒的