C에서 큰 nPr을 계산하는 방법?

Question

C에서 두 숫자의 nPr을 계산하는 함수를 작성했습니다. 큰 숫자를 처리하기 위해이 함수를 적용 할 수 있습니까?

저는 1x10^12까지의 값을 계산할 수 있어야합니다. 저는 다양한 데이터 유형을 시도했으며 매우 고생했습니다! 어떤 차이를 보이지 않았다 그러나

도 내가

long long nPr(long long int n, long long int k); 
long long nPr(long long int n, long long int k){ 

    if (n < 0){ 
     printf("\nERROR - n is less than 0\n\n"); 
     return -1; 
    } 

    if (k > 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; 
    } 
} 

을 시도 이들은 repition없이 순열 있습니다 :

#include<stdio.h> 
    #include<math.h> 

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 < 0){ 
      printf("\nERROR - n is less than 0\n\n"); 
      return -1; 
     } 

     if (k > 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; 
     } 
    } 

감사

J

UPDATE

Answer 1

GMP 라이브러리를 사용하여 bignums을 사용하여 계산할 수 있습니다. C++로 전환하면 the C++ class interface to GMP을 사용하여 bignum에도 익숙한 a+b 표기법을 사용할 수 있습니다. 순수한 C 언어에 머물러 있다면 특정 루틴을 신중하게 사용해야합니다. 추가로 mpz_add.

일부 언어 (예 : Common Lisp)는 기본 숫자를 처리하는 소스 코드를 수정할 필요없이 기본적으로 bignum을 지원합니다. SBCL으로 시도 할 수 있습니다 (적어도 Linux에서는).

물론 bignum 산술 (매우 복잡한 주제)은 원시 산술보다 느립니다.

Bignum은 기본적으로 C에서 지원되지 않으므로 라이브러리를 사용해야합니다 (또는 비현실적인 자체 구현 : bignum에 적합한 알고리즘은 이해하기 어렵고 구현하기가 쉽기 때문에 기존 라이브러리를 사용하는 것이 좋습니다) .

추신. long long은 여전히 ​​도움이되지 않습니다. 64 비트이기 때문입니다. 일부 GCC 컴파일러와 대상 프로세서는 __int128 즉 128 비트 정수를 지원할 수 있지만 실제로는 bignum이 필요합니다.

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