25

我正在尝试计算 100！（即 100 的阶乘）。

我正在寻找使用 C 来完成此任务的最简单方法。我已经阅读过，但没有找到具体的答案。

如果你必须知道，我在 Mac os X 中用 Xcode 编程。

4

4 回答 4

29

如果您正在寻找一个简单的库，libtommath（来自 libtomcrypt）可能是您想要的。

如果您想自己编写一个简单的实现（作为学习练习，或者因为您只需要非常有限的 bigint 功能子集，并且不想依赖于大型库、命名空间污染等） ，那么我可能会针对您的问题提出以下建议：

由于您可以根据 来限制结果的大小，因此n只需预先分配一个uint32_t所需大小的数组来保存结果。我猜你会想要打印结果，所以使用 10 的幂（即基数 1000000000）而不是 2 的幂是有意义的。也就是说，数组的每个元素都是允许的保存 0 到 999999999 之间的值。

要将此数字乘以（正常，非大）整数n，请执行以下操作：

uint32_t carry=0;
for(i=0; i<len; i++) {
    uint64_t tmp = n*(uint64_t)big[i] + carry;
    big[i] = tmp % 1000000000;
    carry = tmp / 1000000000;
}
if (carry) big[len++] = carry;

如果您知道n永远不会大于 100（或其他一些小数字）并且想要避免进入 64 位范围（或者如果您在 64 位平台上并且想要uint64_t用于您的 bigint 数组），那么使基数为 10 的较小幂，以便乘法结果始终适合类型。

现在，打印结果就像这样：

printf("%lu", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.9lu", (long)big[i-1]);
putchar('\n');

如果您想使用 2 的幂作为基数，而不是 10 的幂，则乘法会变得更快：

uint32_t carry=0;
for(i=0; i<len; i++) {
    uint64_t tmp = n*(uint64_t)big[i] + carry;
    big[i] = tmp;
    carry = tmp >> 32;
}
if (carry) big[len++] = carry;

但是，以十进制打印您的结果不会那么愉快...... :-) 当然，如果您想要十六进制的结果，那么这很容易：

printf("%lx", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.8lx", (long)big[i-1]);
putchar('\n');

希望这可以帮助！我将把实现其他东西（如加法、2 个 bigint 的乘法等）作为练习留给你。回想一下您在小学时是如何学习以 10 为底的加法、乘法、除法等并教计算机如何做到这一点的（但以 10 ^ 9 或 2 ^ 32 为底），您应该没问题。

于 2010-07-27T07:05:43.343 回答
9

如果您愿意使用库实现，标准的实现似乎是GMP

mpz_t out;
mpz_init(out);
mpz_fac_ui(out,100);
mpz_out_str(stdout,10,out);

应该算100！从查看文档。

于 2010-07-27T03:44:23.737 回答
2

你要求最简单的方法来做到这一点。所以，给你：

#include <gmp.h>
#include <stdio.h>

int main(int argc, char** argv) {
    mpz_t mynum;
    mpz_init(mynum);
    mpz_add_ui(mynum, 100);
    int i;
    for (i = 99; i > 1; i--) {
        mpz_mul_si(mynum, mynum, (long)i);
    }
    mpz_out_str(stdout, 10, mynum);
    return 0;
}

我测试了这段代码，它给出了正确的答案。

于 2010-07-27T03:44:58.637 回答
2

您还可以使用OpenSSL bn；它已经安装在 Mac OS X 中。

于 2010-07-27T03:50:59.477 回答