在C中计算大数的阶乘

在我的C代码中，我想计算1到100范围内的数字的阶乘。对于小数字，该函数可以工作，但对于更大的数字，例如100！ 它返回错误的结果。 有什么方法可以处理C中的大数阶因子？ 我正在使用的编译器是gcc v4.3.3。 我的代码如下：

#include  #include  double print_solution(int); int main(void) { int no_of_inputs,n ; int ctr = 1; scanf("%d",&no_of_inputs); //Read no of inputs do { scanf("%d",&n); //Read the input printf("%.0f\n",print_solution(n)); ctr++; }while(ctr <= no_of_inputs); return 0; } double print_solution(int n) { if(n == 0 || n == 1) return 1; else return n*print_solution(n-1); } 

Answer 1

没有标准C数据类型可以准确处理大到100的数字！ 如果要通过库或自己完成任意精度整数运算 ，这是唯一的选择。

如果这只是一些爱好项目，我建议你自己尝试一下。 这是一种有趣的运动。 如果这与工作相关，请使用预先存在的库。

您通常会获得的最大C数据类型是64位整数。 100！ 大约为10 ¹⁵⁷ ，其中500位的较好部分准确地存储为整数。

Answer 2

100阶乘是巨大的，准确地说是93326215443944152681699238856266700490715968264381621468592963895217 59999322991560894146397615651828625369792082722375825118521091686400 00000000000000000000。

也许你应该使用像GMP这样的bignum库。 它有很好的文档，一个非常一致的界面，速度，如果你在Linux上你的发行版可能有一个包（我认为我默认安装它）

Answer 3

要近似计算大数的阶乘，您可以这样：

 N！  = n *（n-1）！
所以log（n！）= log（n）+ log（n-1！）

现在，您可以使用动态编程来计算log（n！）并进行计算
N！ as（base）^（log-value）

Answer 4

如果你不想使用bigint库，那么使用stdlib最好的方法是使用math.h long double和tgammal() ：

 long double fact(unsigned n) { return tgammal(n + 1); } 

这会让你100! 在x86上精度为18位小数（即80位long double ）。

确切的实现也不是那么复杂：

 #include  #include  #include  void multd(char * s, size_t len, unsigned n) { unsigned values[len]; memset(values, 0, sizeof(unsigned) * len); for(size_t i = len; i--; ) { unsigned x = values[i] + (s[i] - '0') * n; s[i] = '0' + x % 10; if(i) values[i - 1] += x / 10; } } void factd(char * s, size_t len, unsigned n) { memset(s, '0', len - 1); s[len - 1] = '1'; for(; n > 1; --n) multd(s, len, n); } int main(void) { unsigned n = 100; size_t len = ceill(log10l(tgammal(n + 1))); char dstr[len + 1]; dstr[len] = 0; factd(dstr, len, n); puts(dstr); } 

Answer 5

每个人都在告诉你正确的答案，但还有几点。

1. 您最初使用double来获得更宽范围的想法是行不通的，因为double不能精确地存储这些数据。 它可以进行计算，但需要进行大量舍入。 这就是bigint库存在的原因。

2. 我知道这可能是教程或示例网站的一个例子，但做无限递归会在某些时候咬你。 您有一个基本上是迭代过程的递归解决方案。 您将了解为什么当您尝试使用较大的值运行程序时，此站点的名称是什么（尝试10000）。

一种简单的迭代方法如下

  int answer, idx; for (answer = 1, idx = 1; idx <= no_of_inputs; idx++ ) { answer = answer * idx; } printf("Factorial of %3d = %d\n", no_of_inputs, answer); 

Answer 6

这是我几年前解决谷歌谜语所做的，它使用GMP库http://gmplib.org/ ：

 #include  #include "gmp.h" void fact(mpz_t r,int n){ unsigned int i; mpz_t temp; mpz_init(temp); mpz_set_ui(r,1); for(i=1;i<=n;i++){ mpz_set_ui(temp,i); mpz_mul(r,r,temp); } mpz_clear(temp); } int main(void) { mpz_t r; mpz_init(r); fact(r,188315); /* fact(r,100); */ gmp_printf("%Zd\n",r); mpz_clear(r); return(0); } 

gcc -lgmp -o fact fact.c

。/事实

Answer 7

您可以尝试使用“unsigned long long”类型，但这是内置类型可以获得的最大值。 我建议（正如cletus已经提到的那样）要么采用已知的大数字实现，要么自己编写一个。 “这是一个很好的运动”x 2。

Answer 8

如果您只想使用标准数据类型而不需要确切的答案，那么计算n的对数！ 而不是n！ 本身。 n的对数！ 很容易适合double （除非n很大）。

Answer 9

有什么办法在C中处理大数的阶乘？

因为阶乘可以快速超过标准固定宽度整数的范围甚至浮点类型（如double ，Code应考虑允许无限整数精度的用户类型以获得精确答案。

存在各种宽整数精度库，但如果代码需要简单的解决方案，请考虑使用字符串 。

下面的内容不是很快，也不是数组界限，而是说明了这个想法。 将'0'-'9'转换为0-9这么多是浪费，但这确实可以轻松地逐步调试。

 #include  #include  #include  static char *strfact_mult(char *s, unsigned x) { unsigned sum = 0; size_t len = strlen(s); size_t i = len; while (i > 0) { sum += (s[--i] - '0') * x; s[i] = sum % 10 + '0'; sum /= 10; } while (sum) { len++; memmove(&s[1], s, len); s[i] = sum % 10 + '0'; sum /= 10; } return s; } char *str_fact(char *dest, unsigned n) { strcpy(dest, "1"); while (n > 1) { strfact_mult(dest, n--); } return dest; } void test_fact(unsigned n) { char s[1000]; printf("%3u %s\n", n, str_fact(s, n)); } int main(void) { test_fact(0); test_fact(4); test_fact(54); test_fact(100); } 

产量

  0 1 4 24 54 230843697339241380472092742683027581083278564571807941132288000000000000 100 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 

Answer 10

我猜那是因为你的int范围溢出，大约是。 20亿。 如果使用unsigned int，最多可以获得40亿，但除此之外，您必须使用bigint库 。

Answer 11

100！ = 933262154439441526816992388562667004907159682643816214685929 6389521759999322991560894146397156518286253697920827223758251185210 916864000000000000000000000000

你不能用int或long来表示这么大的数字。

Answer 12

这肯定是由于溢出造成的。 你需要一种方法来表示大数字（ unsigned long long甚至不会覆盖25个！）。

Answer 13

除了别人的建议之外，我建议你熟悉基本类型（int，long，long long，…）的存储限制，无论你实际使用的是什么计算机/平台。 （“如有疑问，请打印出更多！”）

之前的一张海报提到了80位精度限制，但这特别适用于x86 CPU。

另一个人多次引用ISO C90，尽管C99是最新标准; 即使许多编译器还没有完全实现C99，你可能会发现它们很可能至少支持long long，这应该对应于> = 64位精度。

Answer 14

在没有任何外部库的情况下计算大因子

_{这真是一个老问题。 我看到大多数答案表明外部库或近似结果 ，显示内存限制。 但是，想一想略有不同 – 你不必总是在编程中使用integer或double或unsigned long long数来进行数学integer ！}

---

我使用int[]来计算Big Factorials 。 这个小的Java代码可以（理论上）找出任何数字的阶乘 –

 public class BigFactorial { public static int[] calculateFactorial(int inputNumber) { int[] factorial = initializeFactorial(inputNumber); for(int i=inputNumber-1, j, k; i>0; i--){ for(j=factorial.length-1, k=0; factorial[j] >= 0; j--){ k += i*factorial[j]; factorial[j] = k%10; k /= 10; } factorial[j] = k%10; k /= 10; factorial[j-1] = k; for(j=0; factorial[j]<1; j++){ factorial[j] = -1; } } return factorial; } private static int[] initializeFactorial(int inputNumber){ int digits = (int) Math.ceil(inputNumber*Math.log10(inputNumber/2))+2; int[] factorial = new int[digits+1]; for(int i=0; i0; j--){ factorial[j] = i%10; i /= 10; } return factorial; } public static void showOutput(int[] factorial){ int i=0; while(factorial[i]<1){ i++; } for(; i 

Answer 15

不要使用我认为的递归算法，它超级慢，即使它被缓存它也会很慢。 这只是你应该考虑的事情。

这样做的原因是当你调用fact（100）时你实际上没有运行100次，你实际运行该函数5050次。 哪个是坏的，如果它被缓存然后它可能是100次，但是，使用if语句运行函数调用然后运行循环仍然更慢。

 double print_solution(int n) { double rval = 1; unsigned int i; for( i = 1; i <= n; i++ ) { rval *= i; } return rval; } 

使用仲裁精度算法可以使它变得非常高，但是，您需要使用库来执行此操作，或者您可以创建自己的库，但这需要花费大量时间。