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

Question

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

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

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

Answer 1

如果您正在寻找一个简单的库，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 for your bigint array)，然后将基数设置为 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 代替），你应该没问题。

Answer 2

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

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

应该计算 100！通过查看文档。

Answer 3

您要求使用最简单的方法来执行此操作。所以，你开始吧：

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

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

Answer 4

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

Answer 5

您只需 30 行代码即可在 C 中打印阶乘 1000， 和 char 类型：

#include <stdio.h>
#define B_SIZE 3000 // number of buffered digits

struct buffer {
    size_t index;
    char data[B_SIZE];
};

void init_buffer(struct buffer *buffer, int n) {
    for (buffer->index = B_SIZE; n; buffer->data[--buffer->index] = (char) (n % 10), n /= 10);
}

void print_buffer(const struct buffer *buffer) {
    for (size_t i = buffer->index; i < B_SIZE; ++i) putchar('0' + buffer->data[i]);
}

void natural_mul_buffer(struct buffer *buffer, const int n) {
    int a, b = 0;
    for (size_t i = (B_SIZE - 1); i >= buffer->index; --i) {
        a = n * buffer->data[i] + b;
        buffer->data[i] = (char) (a % 10);
        b = a / 10;
    }
    for (; b; buffer->data[--buffer->index] = (char) (b % 10), b /= 10);
}

int main() {
    struct buffer number_1 = {0};
    init_buffer(&number_1, 1);
    for (int i = 2; i <= 100; ++i)
        natural_mul_buffer(&number_1, i);
    print_buffer(&number_1);
}

您会发现速度更快，但“小”Factorial(10000) 在这里立即计算出来。

您可以将其放入 fact.c 文件中，然后编译+执行：

gcc -O3 -std=c99 -Wall -pedantic fact.c ; ./a.out ;

如果您想执行一些基本转换，可以使用 解决方案，另请参阅斐波那契(10000)，谢谢。