如何对大数求和？

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。

输入13，结果2455009817，预期6749977113
输入14，结果3733955097，预期93928268313
输入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;
}

Answer 1

您可以使用 double，尤其是当您的平台使用 IEEE754 时。

这样的 double 为您提供 53 位精度，这意味着整数精确到 2 的 53 次方。对于这种情况来说已经足够了。

如果您的平台不使用 IEEE754，请查阅有关所采用的浮点方案的文档。可能就足够了。

Answer 2

在实践中，您需要一些 arbitrary precision arithmetic (a.k.a. bigint or bignum) library. My recommendation is GMPlib but there are other ones。

不要尝试编写自己的 bignum 库。存在高效和聪明的算法，但它们不直观且难以掌握（您可以找到专门讨论该问题的整本书）。此外，像 GMPlib 这样的现有库正在利用标准 C 编译器不会发出（来自纯 C 代码）的特定机器指令（例如 ADC -add with carry）。

如果这是一项家庭作业，并且不允许您使用外部代码，请考虑以基数或 radix 1000000000（十亿）表示一个数字，并以一种非常天真的方式自己编写操作代码，类似于你小时候学到的东西。但请注意，存在更高效的算法（并且真正的 bignum 库正在使用它们）。

一个数字可以在基数 1000000000 中表示为一个 unsigned 的数组，每个数组都是基数 1000000000 的 "digit"。所以你需要管理数组（可能是堆分配的，使用 malloc) 和它们的长度。

Answer 3

当您刚刚超过 MaxInt 的限制时，一种简单的方法是对合适的 n 进行模 10^n 的计算，并且您进行与浮点计算相同的计算，但是您将所有内容除以 10^ r.The 前一个结果会给你前 n 个数字，而后一个结果会给你答案的最后一个数字，前 r 个数字被删除。那么这里的最后几位会因为舍入误差不准确，所以你应该选择比n小一点的r。在这种情况下，取 n = 9 和 r = 5 会很好。

如何对大数求和？

How to sum large numbers?

c

largenumber

c89