c - 在 C 中实现 bigint 的最简单方法是什么？

Question

我正在尝试计算 100! (即 100 的阶乘)。

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

如果你一定要知道，我在 Mac os X 中使用 Xcode 编程。

Answer 1

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

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

由于您可以根据 n 限制结果的大小，只需预先分配一个所需大小的 uint32_t 数组来保存结果。我猜你会想要打印结果，所以使用 10 的幂(即 base 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 个 bigints 的乘法等)作为练习留给您。回想一下你在小学时是如何学习以 10 为基数的加法、乘法、除法等并教计算机如何做的(但以 10^9 或 2^32 为基数)你应该没问题。