メタ整数正方根の無限再帰

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に）無限再帰を引き起こしていると私はワット間違っているかを把握することができません：再帰的自己それを呼び出すテンプレート構造体の中にそれを変換するのは難しいということコードここでエラーがある：

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