¿Cómo calcular nPr grande en C?

He escrito una función para calcular el nPr de dos números en C, ¿puede ayudarme a adaptarlo para manejar números grandes?

Necesito poder calcular un valor de hasta 1×10 ^ 12. ¡He probado muchos tipos de datos diferentes y estoy muy atascado!

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

Gracias

J

ACTUALIZACIÓN: Estas son permutaciones SIN reposición,

tambien lo intenté

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

Sin embargo no pareció hacer ninguna diferencia.

Es posible que desee calcular utilizando bignums , tal vez utilizando la biblioteca GMP . Si cambia a C ++, puede usar la conocida notación a a+b incluso para bignums, usando la interfaz de clase C ++ para GMP . Si permanece en C puro, deberá usar cuidadosamente rutinas específicas, por ejemplo, mpz_add para la adición.

Por cierto, algunos idiomas (por ejemplo, Common Lisp ) admiten bignums de forma nativa (sin la necesidad de modificar el código fuente que funciona con números ordinarios). Es posible que desee probar con SBCL (al menos en Linux).

Por supuesto, la aritmética bignum (un tema muy complejo) es más lenta que la aritmética nativa.

Los Bignums no son compatibles de forma nativa en C, necesita usar una biblioteca (o implementarse la suya, lo cual no tiene sentido: los buenos algoritmos para los bignums son difíciles de entender e implementar, por lo que es mejor utilizar una biblioteca existente).

PD. long long realmente no ayudará, ya que todavía es de 64 bits. Algunos comstackdores GCC y procesadores de destino pueden admitir __int128, es decir, enteros de 128 bits, pero realmente necesita bignums.

No es necesario evaluar completamente los factoriales cuando se divide, esto reduce el riesgo de desbordamiento de enteros (además de ser más eficiente):

 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); }