使用对数在 C++ 中计算大整数

Question

我正在阅读 Steven S. Skiena 的《算法设计手册》，偶然发现了对数这个话题。我突然想到，我可以在 !（至少在任何可能的地方）中使用 log(.) 函数，而不是在竞争性编程中使用 python 作为大整数。我编写了几个程序来计算一些大整数（20 位数字）和一个数字的阶乘（我试过 30！ -> 32 位数字）的乘积，猜猜看，答案似乎是正确的！

现在我想让你们告诉我这个想法可能会遇到哪些问题？

我经常看到人们使用 python，特别是为了处理大整数而不必为此使用数组。使用日志进行涉及大量的操作是一个非常简单的想法，但仍未广泛应用于此目的 AFAIK。因此，如果其他人之前已经想到并尝试实施它，他们可以告诉我我可能面临的问题。

为了找到阶乘，我的代码是：

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
int i = 30;
long double s = 0;
for (int j = 1; j <= i; ++j)
    s += log(j);
cout << setprecision(300) << exp(s) << endl;
    return 0;
}

Answer 1

cmath中的log函数被重载，具有以下原型

     double log (double x);
      float log (float x);
long double log (long double x);
     double log (T x);     // additional overloads for integral types

log 函数将任何输入转换为 double，然后 returns 你又是另一个 double 或 float 或 long double。

当你使用log时，你基本上是在用浮点数进行计算。这有一些问题。

如果您输入的数字 x 大于 double 或 long double 可以容纳的数字，则无法正确输入。
如果输出大于 double 或 long double 可以容纳的输出，则无法正确转换输出
浮点计算不准确。试试做 0.1 + 0.2 == 0.3
您的程序受到浮点精度的限制。不能有无限精度的浮点数或大于 1.8e308

即使您不喜欢数论类的计算并且只想使用一些大数 (< 1.8e308)，那么您最好使用 double 或 long double 作为与使用 log.

相比，计算速度要快得多

如果您需要在不损失精度的情况下使用大数字，那么您将不得不使用一些专门的库，例如 gmp 或像您所说的那样使用数组。

Answer 2

知道了。是的。如果你看到这个输出，在 5!所有输出都必须有尾随零，但其中一些没有。所以 long double s 不能捕获 log(.) 的完整值。 e的不合理性也绝对是造成这种情况的原因之一。

Answer 3

你可以在最后使用字符串。
使用以下方法将您的答案转换为字符串：

string result = to_string(round(exp(s)));

然后打印字符串。

使用对数在 C++ 中计算大整数

big integer calculation in c++ using logarithms

python

c++

biginteger

factorial

logarithm