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

我想计算100!

我正在寻找使用C来实现这一目标的最简单方法。我已阅读但未找到具体答案。

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

谢谢!

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

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

由于您可以基于n绑定结果的大小,只需预先分配一个所需大小的uint32_t数组来保存结果。 我猜你要打印结果,所以使用10的幂(即基数1000000000)而不是2的幂是有意义的。也就是说,允许你的数组的每个元素保持0到999999999之间的值。

要将此数字乘以(正常,非大)整数n ,请执行以下操作:

 uint32_t carry=0; for(i=0; i 

如果你知道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> 32; } if (carry) big[len++] = carry; 

但是,以十进制打印结果不会那么令人愉快... :-)当然如果你想要hex的结果,那么很容易:

 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而不是)你应该没问题。

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

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

应该算100! 从查看文档。

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

您要求最简单的方法来执行此操作。 所以,你走了:

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

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