C语言 在 C 中实现 bigint 的最简单方法是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3340511/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the simplest way of implementing bigint in C?
提问by AlexBrand
I am trying to calculate 100!
我正在尝试计算 100！
I am looking for the simplest way to accomplish this using C. I have read around but have not found a concrete answer.
我正在寻找使用 C 完成此任务的最简单方法。我已经阅读了一些内容，但还没有找到具体的答案。
If you must know, I program in Xcode in Mac os X.
如果你一定要知道，我在 Mac os X 中用 Xcode 编程。
Thanks!
谢谢！
回答by R.. GitHub STOP HELPING ICE
If you're looking for a simple library, libtommath (from libtomcrypt) is probably what you want.
如果您正在寻找一个简单的库，libtommath（来自 libtomcrypt）可能就是您想要的。
If you're looking to write a simple implementation yourself (either as a learning exercise or because you only need a very limited subset of bigint functionality and don't want to tack on a dependency to a large library, namespace pollution, etc.), then I might suggest the following for your problem:
如果您想自己编写一个简单的实现（作为学习练习，或者因为您只需要非常有限的 bigint 功能子集，并且不想依赖于大型库、命名空间污染等） ，那么我可能会针对您的问题提出以下建议：
Since you can bound the size of the result based on n, simply pre-allocate an array of uint32_tof the required size to hold the result. I'm guessing you'll want to printthe result, so it makes sense to use a base that's a power of 10 (i.e. base 1000000000) rather than a power of 2. That is to say, each element of your array is allowed to hold a value between 0 and 999999999.
由于您可以基于 来限制结果的大小，因此n只需预先分配一个uint32_t所需大小的数组来保存结果。我猜你会想要打印结果，所以使用 10 的幂（即基数 1000000000）而不是 2 的幂的基数是有意义的。也就是说，数组的每个元素都是允许的保持一个介于 0 和 999999999 之间的值。
To multiply this number by a (normal, non-big) integer n, do something like:
要将这个数字乘以 (normal, non-big) integer 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;
If you know nwill never be bigger than 100 (or some other small number) and want to avoid going into the 64-bit range (or if you're on a 64-bit platform and want to use uint64_tfor your bigint array), then make the base a smaller power of 10 so that the multiplication result will always fit in the type.
如果您知道n永远不会大于 100（或其他一些小数字）并希望避免进入 64 位范围（或者如果您在 64 位平台上并希望uint64_t用于您的 bigint 数组），那么将基数设为 10 的较小幂，以便乘法结果始终适合该类型。
Now, printing the result is just something like:
现在，打印结果就像：
printf("%lu", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.9lu", (long)big[i-1]);
putchar('\n');
If you want to use a power of 2 as the base, rather than a power of 10, the multiplication becomes much faster:
如果您想使用 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;
However, printing your result in decimal will not be so pleasant... :-) Of course if you want the result in hex, then it's easy:
但是，以十进制打印结果不会那么令人愉快...... :-) 当然，如果你想要十六进制的结果，那么这很容易：
printf("%lx", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.8lx", (long)big[i-1]);
putchar('\n');
Hope this helps! I'll leave implementing other things (like addition, multiplication of 2 bigints, etc) as an exercise for you. Just think back to how you learned to do base-10 addition, multiplication, division, etc. in grade school and teach the computer how to do that (but in base-10^9 or base-2^32 instead) and you should have no problem.
希望这可以帮助！我将实现其他事情（如加法、2 个 bigint 的乘法等）作为您的练习。回想一下你在小学是如何学会做基数 10 加法、乘法、除法等的，然后教计算机如何做（但用基数 10^9 或基数 2^32），你应该没有问题。
回答by Scott Wales
回答by lhf
You can also use OpenSSL bn; it is already installed in Mac OS X.
您也可以使用OpenSSL bn；它已经安装在 Mac OS X 中。
回答by Borealid
You asked for the simplestway to do this. So, here you go:
你要求最简单的方法来做到这一点。所以，给你：
#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;
}
I tested this code and it gives the correct answer.
我测试了这段代码，它给出了正确的答案。
