在C中避免使用置换（nPr，nCr）函数的整数溢出
我试图做一些与统计相关的function，所以我可以执行一些相关的程序（即：概率的统计计算，生成任意深度的Pascal三角形等）。
我遇到了一个问题，我可能会遇到溢出问题。 例如，如果我想计算nPr（n = 30，p = 1），我知道我可以将它减少到：
30P1 = 30! / (30 - 1)! = 30! / (29)! = 30! / 29! = 30 但是，在使用下面的函数进行计算时，由于整数溢出，我看起来总是会得到无效值。 是否有任何变通方法不需要使用库来支持任意大数字？ 我已经在其他关于伽玛函数的post中读过一些内容，但找不到具体的例子。
int factorial(int n) { return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n; } int nCr(int n, int r) { return (nPr(n,r) / factorial(r)); //return factorial(n) / factorial(r) / factorial(nr)); } int nPr(int n, int r) { return (factorial(n) / factorial(nr)); }
你看起来像是在正确的轨道上，所以你走了：
#include #include int nCr(int n, int r) { if(r>n) { printf("FATAL ERROR"); return 0; } if(n==0 || r==0 || n==r) { return 1; } else { return (int)lround( ((double)n/(double)(nr)/(double)r) * exp(lgamma(n) - lgamma(nr) - lgamma(r))); } } int nPr(int n, int r) { if(r>n) {printf("FATAL ERROR"; return 0;} if(n==0 || r==0) { return 1; } else { if (n==r) { r = n - 1; } return (int)lround( ((double)n/(double)(nr)) * exp(lgamma(n) - lgamma(nr))); } }
要编译，请执行： gcc -lm myFile.c && ./a.out
请注意，结果的准确性受double精度数据类型的位深度限制。 您应该能够获得良好的结果，但要注意：用long long unsigned替换上面的所有int可能不一定能保证n,r较大值的准确结果。 在某些时候，您仍然需要一些数学库来处理任意大的值，但这应该可以帮助您避免使用较小的输入值。
我认为你有两个选择：
-
使用大整数库。 这样你就不会失去精确度（浮点可能适用于某些情况，但是它是一个糟糕的替代品）。
-
重构您的function，因此它们不会达到高中间值。 例如，
factorial(x)/factorial(y)是从y+1到x的所有数字的乘积。 所以只需编写一个循环并乘以。 这样，如果最终结果溢出，您将只获得溢出。
如果您不必处理有符号值（并且看起来没有这样做），您可以尝试使用更大的整数类型，例如， unsigned long long 。 如果这还不够，则需要使用支持任意长整数的非标准库。 请注意，使用long long类型需要C99编译器支持（如果使用GCC，可能必须使用-std=c99进行编译）。
编辑：您可以将更多内容放入一个long double ，在某些系统上为80位。
我可能会变得很密集，但在我看来， double并且伽玛函数在这里是过度的。
是否有任何变通方法不需要使用库来支持任意大数字？
当然有。 你完全知道你在处理什么 – 整数范围的产品。 一系列整数是有限整数列表的特例。 我不知道用C表示列表的惯用方法是什么，所以我会坚持使用C-ish伪代码：
make_list(from, to) return a list containing from, from+1, ..., to concatenate_lists(list1, list2) return a list with all the elements from list1 and list2 calculate_list_product(list) return list[0] * list[1] * ... * list[last] calculate_list_quotient(numerator_list, denominator_list) /* be a bit clever here: form the product of the elements of numerator_list, but any time the running product is divisible by an element of denominator_list, divide the running product by that element and remove it from consideration */ n_P_r(n, r) /* nPr is n! / (nr)! which simplifies to n * n-1 * ... * r+1 so we can just: */ return calculate_list_product(make_list(r+1, n)) n_C_r(n, r) /* nCr is n! / (r! (nr)!) */ return calculate_list_quotient( make_list(1, n), concatenate_lists(make_list(1, r), make_list(1, nr)) )
请注意，我们从未实际计算过阶乘！
这是一种不使用伽玛函数计算的方法。 它依赖于n_C_r =（n / r）*（（n-1） C （r-1））以及任何正值n_C_0 = 1的事实，因此我们可以使用它来编写如下所示的recusrive函数
public long combination(long n, long r) { if(r==0) return 1; else { long num = n * combination(n - 1, r - 1); return num/r; } }