如何求解大数之和？

Question

我正在尝试计算1 + 1 * 2 + 1 * 2 * 3 + 1 * 2 * 3 * 4 + ... + 1 * 2 * ... * n，其中n是用户输入的。它适用于n值最多为12。我想计算n=13，n=14和n=15的总和。如何在C89中实现呢？据我所知，我只能在C99或C11中使用unsigned long long int。

1. 输入13，结果2455009817，预期6749977113
2. 输入14，结果3733955097，预期93928268313
3. 输入15，结果1443297817，预期1401602636313

我的代码：

#include <stdio.h>
#include <stdlib.h>
int main()
{
    unsigned long int n;
    unsigned long int P = 1;
    int i;
    unsigned long int sum = 0;
    scanf("%lu", &n);
    for(i = 1; i <= n; i++)
    {
        P *= i;
        sum += P;
    }
    printf("%lu", sum);
    return 0;
}

- Timʘtei

---

你可以考虑使用外部库，比如GMP（https://gmplib.org/）。 - Federico klez Culloca

我不理解为什么会被踩。要求很明确，而且还提供了一个好的可编译示例。 - Bathsheba

@Bathsheba：没有做研究的努力是一个合理的数据验证（DV）原因。在谷歌或维基百科上搜索“unsigned long range”并不算过分。 - too honest for this site

好的，我正在制定一种更好的技术来提高ns。给我一些时间。 - Pushan Gupta

您的程序在64位系统上给出了预期结果。也就是说，除非您正在使用Windows系统。（参见链接：https://dev59.com/mHRC5IYBdhLWcg3wMd5S） - Edgar Bonet

Answer 1

实际上，您需要一些任意精度算术（也称为大整数或bignum）库。我的建议是GMPlib，但还有其他选择。

不要尝试编写自己的bignum库。虽然存在高效且聪明的算法，但它们并不直观，很难理解（您可以找到专门讨论这个问题的整本书）。此外，现有的库如GMPlib正在利用特定的机器指令（例如ADC-带进位加法），而标准C编译器不会从纯C代码中发出。

如果这是一份作业，且你不被允许使用外部代码，可以考虑例如将数字表示为基数或者进制1000000000（十亿），并以类似于儿童学习的方式编写操作。但请注意，存在更有效率的算法（真正的大整数库正在使用它们）。

一个数字可以通过拥有一个unsigned数组来在基数1000000000下进行表示，每个数组元素代表基数1000000000下的一个“数字”。因此，您需要管理数组（可能使用malloc进行堆分配）及其长度。

- Basile Starynkevitch

---

这里有一些很好的建议。我不理解为什么会被踩，是时候改变这种情况了！ - Bathsheba

@chtz：“我不知道在解释性语言中实现BN库是否是一个好主意。”- 这完全是离题了，但是，偶尔我们可以有一些离题的乐趣。现代高性能动态优化器非常不直观。例如，有一个Ruby gem用于操作PSD（Photoshop文件）。它是作为高度优化的C扩展实现的（适用于支持它们的Ruby实现），以及纯粹的、惯用的Ruby“回退”实现（适用于不支持C扩展的实现，如AOT编译器Topaz）。 - Jörg W Mittag

...ECMAScript）。这个纯Ruby回退实现几乎可以想象到的一切都能抵制被优化。例如，从存储在运行时字符串中的方法名称动态调用方法等。循环遍历方法名数组并反射调用它们。因此，您可能认为这不可能快速完成。但是，关键在于：正是因为它是用Ruby编写的，TruffleRuby优化解释器可以通过多轮内联、专门化和优化将整个测试程序编译成一个常量！ - Jörg W Mittag

使用TruffleRuby比使用C扩展快得多，因为跨越Ruby-C边界是昂贵的。而TruffleRuby可以在测试程序（用Ruby编写）、PSD库（用Ruby编写）和Ruby核心数据结构（用Ruby编写）之间自由地进行内联，而YARV没有任何可用的东西：YARV只知道如何快速运行Ruby，但代码中的Ruby部分很简单。YARV对Ruby核心数据结构（用C编写）或PSD库（用C编写）没有深入了解。GCC无法优化Ruby代码，因为它不知道它。而且从Ruby调用每个函数时... - Jörg W Mittag

PSD库是VM边界的昂贵越过。最终，消除那些跨语言调用可以为您节省更多成本，比起使用Ruby编写计算密集型代码时可能会失去的一切。因此，我不认为“在解释性语言中实现BN库”是非常荒谬的。内联计算密集型代码到更大的应用程序中的能力不可低估。 - Jörg W Mittag

Answer 2

如果你的平台使用IEEE754，你可以使用double类型。

double类型可以提供53位精度，这意味着整数可以精确表示到2的53次方。这对于这种情况已经足够了。

如果你的平台没有使用IEEE754，请查阅关于所采用浮点数方案的文档。它可能是适当的。

- Bathsheba

---

请注意，与 BigInt 解决方案不同的是，这种方法在某一点以后会失去精度。 - BallpointBen

确实如此。在IEEE754标准下，53次方后便会出现这种情况。但内置的整型也会有类似问题。因此你需要选择适合你工作的正确类型。 - Bathsheba

Answer 3

当你的计算超过MaxInt的限制时，一种简单的方法是对10^n取模来进行计算，其中n是合适的数字，与浮点运算相同，但将每个数都除以10^r。前一个结果将给出前n个数字，而后一个结果将给出答案的后几位数字，但会删除前r个数字。由于舍入误差，最后几位数字可能不准确，所以你应该选择一个比n稍小的r。在这种情况下，取n=9和r=5效果很好。

- Count Iblis