C++ 处理大数

Question

好的，我必须为我的 c++ class 做一些简单的任务。两个函数，第一个是斐波那契数列，第二个是一些随机数列（求 e）。它看起来像这样：

#include <stdio.h>
#include <cstdlib>
#include <string>
#include <math.h>

void fib(int number)
{
    int a=0, b=1;
    printf("%d\n", a); 
    for (; number>0; number--)
    {
        printf("%d\n", b);
        b+=a;
        a = b-a;
    }
}

void e_math(unsigned int number)
{
    for (double n = 1; number>0; number--, n++)
    {
        printf("%f\n", pow((1+1/n), n));
    }
}

int main(int argc, char** argv)
{
    if (std::string(argv[2])=="f") fib(atoi(argv[1])-1);
    if (std::string(argv[2])=="c") e_math(atoi(argv[1])-1);
    else printf("Bad argument\n");
}

所以最后我做了 g++ main.cpp -o app;./app 10 f。它工作得很好。但是当我想：嗯，也许让我们检查更大的数字，然后添加 50 它就搞砸了。我的意思是它对大约 40 个序列号（用 Python 检查）很好，但后来它开始 printf() 负片等。我认为它可能在 int 范围内。所以我将 int a=0, b=1 更改为 long long a=0, b=1，但它仍然打印相同（我仍然使用 printf("%d..)，因为 %lld 不起作用

Answer 1

第 n 个 Fibonacci number 在 1.6^n 左右，这对 n=50 来说是一个很大的数字（它是 53316291173）。您也许可以将其表示为 long，但随着事物呈指数增长，您将无法将 Fn 用于大型 n 存储为原始数据类型（其中 Fn表示第n个斐波那契数）：第n+1个斐波那契数大约是第n个斐波那契数的1.6倍。

您需要大整型数据类型来计算 Fn 以获得大 n。

Answer 2

您可以使用 The GNU Multiple Precision Arithmetic Library. Here the link to the C++ Interface 中的整数类。

编辑：另请参阅 15.7.4 Fibonacci Numbers。

Answer 3

评论中有信息告诉您如何能够正确打印long long，以便您可以从整个范围中受益。但是，正如他在回答中所说的那样，你不会走得更远（它将在无符号 64 位上循环 n=94）。

如果你想处理更大的斐波那契数（事实上，任意大数）你可以使用 boost::multiprecision.

例如：

#include <boost/multiprecision/gmp.hpp>  

boost::multiprecision::mpz_int fib(boost::multiprecision::mpz_int number)
{
    boost::multiprecision::mpz_int a=0, b=1;
    for (; number>0; number--)
    {
        b += a;
        a = b-a;
    }
    return a;
}

int main()
{
    std::cout << fib(500);
}

构建时需要 link 使用 gmp。例如：

g++ -o fib fib.cc -lgmp
./fib
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

Answer 4

由于 %lld 不可移植并且在任何编译器中都不起作用，如果您将 a 和 b 声明为 long and用 c++ std::cout?

打印结果

这是必要的，因为第 50 个斐波那契数是 7778742049，它大于典型的最大正整数值（32 位）2147483647。

顺便说一句，你应该删除最后一个 else，我不认为在提供参数 f 时正在做你想做的事情。

这是 code 工作。

C++ 处理大数

C++ Handling big numbers

c++

int

long-integer