무한 재귀 메타의 정수 제곱근

Question

좋은 하루,

내 친구는 메타 함수에 정수 제곱근 함수를 변환에 대해 요구하고있다. 여기에 원래의 함수입니다 :

unsigned isqrt(unsigned value) 
{ 
    unsigned sq = 1, dlt = 3; 
    while(sq<=value) 
    { 
     sq += dlt; 
     dlt += 2; 
    } 
    return (dlt>>1) - 1; 
} 

내가 constexpr를 사용하여 메타 버전을 썼다,하지만 그는 어떤 이유로 새로운 기능을 사용할 수 없습니다 말했다

constexpr std::size_t isqrt_impl 
    (std::size_t sq, std::size_t dlt, std::size_t value){ 
    return sq <= value ? 
     isqrt_impl(sq+dlt, dlt+2, value) : (dlt >> 1) - 1; 
} 

constexpr std::size_t isqrt(std::size_t value){ 
    return isqrt_impl(1, 3, value); 
} 

그래서 나는 그것이 안 생각 하드 재귀 적으로 자기를 호출 템플릿 구조체로 그것을 변환하는 것을 수 :

template <std::size_t value, std::size_t sq, std::size_t dlt> 
struct isqrt_impl{ 
    static const std::size_t square_root = 
     sq <= value ? 
     isqrt_impl<value, sq+dlt, dlt+2>::square_root : 
     (dlt >> 1) - 1; 
}; 

template <std::size_t value> 
struct isqrt{ 
    static const std::size_t square_root = 
     isqrt_impl<value, 1, 3>::square_root; 
}; 

불행하게도,이 (GCC 4.6.1)에 무한 재귀를 일으키는 나는 w 무엇이 잘못되었는지 알아낼 수 없습니까 코드 ith. 여기에 오류 :

C:\test>g++ -Wall test.cpp 
test.cpp:6:119: error: template instantiation depth exceeds maximum of 1024 (use 
-ftemplate-depth= to increase the maximum) instantiating 'struct isqrt_impl<25u 
, 1048576u, 2049u>' 
test.cpp:6:119: recursively instantiated from 'const size_t isqrt_impl<25u, 4u 
, 5u>::square_root' 
test.cpp:6:119: instantiated from 'const size_t isqrt_impl<25u, 1u, 3u>::squar 
e_root' 
test.cpp:11:69: instantiated from 'const size_t isqrt<25u>::square_root' 
test.cpp:15:29: instantiated from here 

test.cpp:6:119: error: incomplete type 'isqrt_impl<25u, 1048576u, 2049u>' used i 
n nested name specifier 

모두 감사합니다,

Answer 1

템플릿 평가는 기본적으로 게으르지 않습니다.

static const std::size_t square_root = 
    sq <= value ? 
    isqrt_impl<value, sq+dlt, dlt+2>::square_root : 
    (dlt >> 1) - 1; 

은 조건에 관계없이 항상 템플릿을 인스턴스화합니다. 해당 솔루션을 작동 시키려면 boost::mpl::eval_if 또는 이와 동등한 것이 필요합니다.

또는 K-ballos 대답처럼 조건이 충족되면 재귀를 중지하는 기본 사례 부분 템플릿 특수화를 사용할 수 있습니다.

부분적으로 전문화 된 게으른 평가의 일부 형식을 사용하는 코드를 선호하는 이유는 실제로 이해하기 쉽고 템플릿이 더 낮은 노이즈를 유지하기 때문입니다.

Answer 2

Unfortunately, this is causing infinite recursion (on GCC 4.6.1) and I am unable to figure out what is wrong with the code.

내가 isqrt_impl에 대한 기본 케이스 전문을 볼 수 없습니다. 이 재귀를 깨기 위해 기본 케이스에 대한 템플릿 전문화가 필요합니다. 다음은 간단한 시도입니다.

template <std::size_t value, std::size_t sq, std::size_t dlt, bool less_or_equal = sq <= value > 
struct isqrt_impl; 

template <std::size_t value, std::size_t sq, std::size_t dlt> 
struct isqrt_impl< value, sq, dlt, true >{ 
    static const std::size_t square_root = 
     isqrt_impl<value, sq+dlt, dlt+2>::square_root; 
}; 

template <std::size_t value, std::size_t sq, std::size_t dlt> 
struct isqrt_impl< value, sq, dlt, false >{ 
    static const std::size_t square_root = 
     (dlt >> 1) - 1; 
};