如何计算C中的大nPr？

我写了一个函数来计算C中两个数的nPr，你能不能帮我调整它来处理大数？

我需要能够计算高达1×10 ^ 12的值 – 我尝试过很多不同的数据类型，而且非常困难！

#include #include int main() { long int n=49,k=6; printf("%li nPr %li = %li\n\n",n,k,nPr(n,k)); return 0; } long nPr(long int n, long int k); long nPr(long int n, long int k){ if (n  n ){ printf("\nERROR - k is greater than n\n\n"); return -1; } else { long int i,result = 1,c=n+1-k; for(i=c; i<=n; i++) { result = result * i; } return result; } } 

谢谢

Ĵ

更新：这些是没有重复的排列，

我也试过了

 long long nPr(long long int n, long long int k); long long nPr(long long int n, long long int k){ if (n  n ){ printf("\nERROR - k is greater than n\n\n"); return -1; } else { long long int i,result = 1,c=n+1-k; for(i=c; i<=n; i++) { result = result * i; } return result; } } 

但它似乎没有任何区别

Answer 1

您可能想要使用bignums进行计算，可能使用GMP库。 如果切换到C ++，即使对于bignums，也可以使用熟悉的a+b表示法，使用G ++的C ++类接口 。 如果你保持纯C，你需要仔细使用特定的例程，例如mpz_add添加。

顺便说一下，一些语言（例如Common Lisp ）原生支持bignums（不需要修改普通数字的源代码）。 您可能想尝试使用SBCL （至少在Linux上）。

当然，bignum算术（一个非常复杂的主题）比本机算术慢。

在C中本身不支持Bignums，你需要使用一个库（或者自己实现它，这是无意义的：bignums的好算法很难理解和实现，所以最好使用现有的库）。

PS。 long long不会真正帮助，因为它仍然是64位。 一些GCC编译器和目标处理器可能支持__int128，即128位整数，但你真的需要bignums。

Answer 2

在划分时，您不需要完全评估因子，这可以降低整数溢出的风险（以及更高效）：

 long factorialDivision(int topFactorial, int divisorFactorial) { long result = 1; int i; for (i = topFactorial; i > divisorFactorial; i--) result *= i; return result; } long factorial(int i) { if (i <= 1) return 1; return i * factorial(i - 1); } long nPr(int n, int r) { // naive: return factorial(n) / factorial(n - r); return factorialDivision(n, n - r); } long nCr(int n, int r) { // naive: return factorial(n) / factorial(r) * factorial(n - r); return nPr(n, r) / factorial(r); }