N K 함수를 선택하면 Rcpp가 충돌합니다.

Question

나는 Rcpp를 통해 R과 인터페이스하는 'n choose k' 함수를 C++로 작성했습니다.어떤 이유로 '0으로 나누기' 런타임 오류가 발생합니다.30을 평가하려고 할 때 2를 선택하려고 하면 이런 일이 발생합니다.

evalCpp를 사용하여 각 줄을 수동으로 평가해 보았지만 여전히 0으로 나누기가 발생하는 위치에 대해 의아해합니다.어쩌면 누군가가 나에게 이것을 지적하거나 K를 선택하는 더 나은 글쓰기 방법을 제안할 수 있을까요?

코드는 다음과 같습니다.

// [[Rcpp::export]]                                                                                                                                  
int chooseC(int n, int k) {                                                                                                                         
  if (k > n) {                                                                                                                                      
    std::cout << "Error. k cannot be greater than n." << std::endl;                                                                                 
    return 0;                                                                                                                                       
  }                                                                                                                                                 
  int factN = std::tgamma(n + 1);                                                                                                                   
  int factK = std::tgamma(k + 1);                                                                                                                   
  int factDiff = std::tgamma(n - k + 1);                                                                                                            
  return factN/(factK*factDiff);                                                                                                                    
} 

Answer 1

간단히:

• 내가 볼 수 있는 한 성병에는 tgamma가 없습니다.

• R 자체는 choose 함수이므로 아래 작업을 수행하겠습니다.

• R에는 감마 분포 등도 있으므로 직접 수행할 수도 있습니다.

• 왜 값을 인쇄하지 않았습니까? factN, factK, factDiff ?

간단한 Rcpp 솔루션:

#include <Rcpp.h>

// [[Rcpp::export]]  
double chooseC(double n, double k) {
  return Rf_choose(n, k);
}

예:

R> chooseC(5,2)     
[1] 10
R> 

편집하다: @Blastfurnace의 댓글에 이어 tgamma() C++11에서 cmath 헤더, 여기 나에게 잘 작동하는 복구된 버전이 있습니다.

#include <Rcpp.h>
#include <cmath>

// [[Rcpp::plugins(cpp11)]]

// [[Rcpp::export]] 
int chooseCtake2(int n, int k) {
  if (k > n) {
    Rcpp::stop("Error. k cannot be greater than n.");
  }
  int factN = std::tgamma(n + 1);
  int factK = std::tgamma(k + 1);
  int factDiff = std::tgamma(n - k + 1);
  return factN/(factK*factDiff); 
}

사용 예:

R> sourceCpp("/tmp/chooseC.cpp")
R> chooseCtake2(2,3)
Error: Error. k cannot be greater than n.
R> chooseCtake2(5,2)
[1] 10
R> 

Answer 2

그래서 std::tgamma(x) x의 감마 함수를 계산합니다.이 함수는 매우 빠르게 무한대로 이동합니다.

http://www.wolframalpha.com/share/clip?f=d41d8cd98f00b204e9800998ecf8427et5pmak8jtn

이미 x == 31에 매우 큰 숫자가 있습니다.

이 매우 큰 double을 다시 int로 변환하면 결과는 정의되지 않은 동작입니다(4.9 부동 정수 변환 [conv.fpint]).

플로팅 포인트 유형의 송금은 정수 유형의 사전으로 변환 될 수 있습니다.변환이 잘립니다.즉, 분수 부분은 폐기됩니다.잘린 값을 대상 유형에 표시 할 수없는 경우 동작이 정의되지 않습니다.

내 시스템에서는 이 변환({30, 2} 입력 사용)으로 인해 값이 -2147483648인 int가 생성됩니다.이는 몇 가지 인쇄 문을 삽입하면 쉽게 확인할 수 있습니다.

int
chooseC(int n, int k)
{
    if (k > n)
    {                                                                                                                                      
        std::cout << "Error. k cannot be greater than n.\n";
        return 0;                                                                                                                                       
    }                                                                                                                                                 
    int factN = std::tgamma(n + 1);
    std::cout << "factN = " << factN << '\n';
    int factK = std::tgamma(k + 1);
    std::cout << "factK = " << factK << '\n';
    int factDiff = std::tgamma(n - k + 1);
    std::cout << "factDiff = " << factDiff << '\n';
    std::cout << "factK*factDiff = " << factK*factDiff << '\n';
    return factN/(factK*factDiff); 
}

나에게는 다음이 출력됩니다.

factN = -2147483648
factK = 2
factDiff = -2147483648
factK*factDiff = 0

볼 수 있듯이, UB는 궁극적으로 0으로 나누는 결과를 가져오며, 이는 또한 UB입니다.그리고 당신이 보고 있는 행동과 매우 유사하게 들립니다.

이 문제에 대한 해결책은 적분 산술만을 사용하여 사물을 계산하고, 최종 결과가 적분 유형으로 표현 가능한 경우 중간 계산이 오버플로되지 않도록 하는 것입니다.이는 최대 공약수 함수의 사용을 수반합니다.

이를 수행하는 오픈 소스 코드는 다음에서 확인할 수 있습니다.

http://howardhinnant.github.io/combinations.html

"count_each_combination"을 검색하세요.당신의 chooseC 으로 코딩할 수 있다 count_each_combination 이렇게:

int
chooseC(int n, int k)
{
    if (k > n)
    {                                                                                                                                      
        std::cout << "Error. k cannot be greater than n.\n";
        return 0;                                                                                                                                       
    }                                                                                                                                                 
    return count_each_combination(n-k, k);
}

지금 chooseC(30, 2) 435를 반환합니다.만약에 count_each_combination 결과를 저장할 수 없습니다. int, ㅏ std::overflow_error 던져 질 것입니다.

제한하고 싶다면 chooseC 에게 k == 2, 또는 알고리즘을 더 잘 이해하기 위해 일시적으로 그렇게 할 수도 있습니다. 조합 계산 공식은 다음과 같습니다.

언제 k == 2, 이는 다음과 같이 단순화됩니다.

n*(n-1)/2

이제 n 짝수이거나 n-1 짝수이다.어느 것을 발견하고 잘림 오류 없이 해당 숫자를 2로 나눈 다음 결과에 2로 나누지 않은 숫자를 곱할 수 있습니다.따라서 적분 연산만을 사용하여 잘림 오류나 중간 오버플로 가능성 없이 정확한 결과를 얻을 수 있습니다.이것이 바로 기술이다. count_each_combination 제공된 정수 유형에 맞을 수 있는 경우 항상 정확한 결과를 제공하기 위해 사용하지만 모든 제수로 일반화됩니다.