अनंत recursion मेटा में पूर्णांक वर्ग मूल

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

तो मैंने सोचा कि ऐसा नहीं होना चाहिए परिणत कि कड़ी करने के लिए टेम्पलेट struct है कि यह रिकर्सिवली स्वयं कहता है कि हो सकता है:

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

दुर्भाग्य से, इस अनंत प्रत्यावर्तन (जीसीसी 4.6.1 पर) खड़ी कर रहा है और मैं यह पता लगाने की क्या गलत हो w है असमर्थ हूँ कोड के साथ। यहाँ त्रुटि है:

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 या उस समाधान के समाधान के बराबर कुछ चाहिए।

वैकल्पिक रूप से आपके पास बेस केस आंशिक टेम्पलेट विशेषज्ञता हो सकती है जो स्थिति को पूरा होने पर रिकर्सन को रोकता है, जैसे के-बॉलोस उत्तर में।

मैं वास्तव में कोड पसंद करता हूं जो आंशिक विशेषज्ञता पर आलसी मूल्यांकन के कुछ रूपों का उपयोग करता है क्योंकि मुझे लगता है कि टेम्पलेट को कम करने वाले शोर को समझना और रखना आसान है।

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