如何总结大数？

Question

我试图来计算1 + 1 * 2 + 1 * 2 * 3 + 1 * 2 * 3 * 4 + ... + 1 * 2 * ... * n,其中n是用户输入.它适用于中值n高达12.我要计算总和n = 13,n = 14和n = 15.我如何在C89中做到这一点？据我所知,我unsigned long long int只能在C99或C11中使用.

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;
}

Answer 1

在实践中,您需要一些任意精度算术(aka bigint或bignum)库.我的建议是GMPlib,但还有其他的.

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

如果这是一个家庭作业,并且不允许使用外部代码,请考虑例如用基数或基数 1000000000(十亿)表示一个数字,并以非常幼稚的方式编写自己的操作,类似于您从孩提时学到的.但要注意存在更有效的算法(并且真正的bignum库正在使用它们).

数字可以通过具有数组来表示为100000000 unsigned,每个数组都是1000000000 的"数字".因此,您需要管理数组(可能是堆分配,使用malloc)及其长度.

Answer 2

您可以使用a double,特别是如果您的平台使用IEEE754.

这样的a double给出了53位的精度,这意味着整数精确到2的53次幂.这对于这种情况来说已经足够了.

如果您的平台不使用IEEE754,请参阅所采用的浮点方案的文档.这可能就足够了.