如何在C语言中实现大整数（bigint）的最简单方法？

Question

如何在C语言中实现大整数（bigint）的最简单方法？

cbigint

27

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

我正在寻找使用C语言完成这个任务最简单的方法。我查阅了一些资料，但没有找到确切的答案。

如果您需要知道，我在Mac OS X中使用Xcode编程。

- AlexBrand

8

这是您要的：933[去掉100个数字]00000 :-) - AndersK

19

@Anders：这个网站是堆栈溢出，而不是评论溢出！ :-O - James McNellis

哈哈，我知道可以在 WolframAlpha 上获取这个值。不过，我正在学习 C 语言，想知道如何实现这个功能。 - AlexBrand

1

在C语言中有“BigInt”吗？ - outis

5个回答

10

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

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

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

- Scott Wales

4

您希望知道最简单的方法来完成这件事。所以，这里有：

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

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

- Borealid

Scott的回答里有一个。 - JeremyP

2

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

- lhf

1

您提供的链接已失效。 - Caltrop

@Caltrop，请参考https://www.openssl.org/docs/man1.0.2/man3/bn.html，但是OpenSSL bn不再安装在Mac OS X中。 - lhf

2

你只需要使用30行代码，包括<stdio.h>和char类型就可以在C语言中打印出1000的阶乘：

#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)，谢谢。

- Michel

3

40行代码就可以实现可读性。 - David C. Rankin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- R.. GitHub STOP HELPING ICE · Accepted Answer

如果你正在寻找一个简单的库，那么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 作为大整数数组），那么将底数设为更小的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');

希望这可以帮到你！我将其他的实现（例如两个大整数的加法，乘法等）留给你作为练习。只需回想起在小学时如何学习使用基数10进行加法、乘法、除法等，并教计算机以相同方式进行操作（但使用基数10^9或基数2^32），你应该不会遇到问题。