nieskończonej rekurencji w Meta Integer pierwiastkowa

Question

Dzień dobry,

Mój znajomy prosi o przekształcenie funkcję pierwiastka kwadratowego liczby całkowitej w meta-funkcji. Oto oryginalna funkcja:

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

Napisałem meta wersję używając constexpr, ale powiedział, że nie można korzystać z nowej funkcji z jakiegoś powodu:

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

Pomyślałem więc nie powinno być trudne do przekształcenia struktury, które do szablonu, który wywołuje to samo rekurencyjnie:

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

Niestety, to powoduje nieskończoną rekurencję (na GCC 4.6.1) i nie jestem w stanie dowiedzieć się, co jest nie tak w z kodem. Tutaj jest błąd:

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 

Dzięki wszystkim

Answer 1

Ocena szablonu nie jest domyślnie leniwą.

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

będzie zawsze tworzyć szablon, niezależnie od warunków. Potrzebujesz boost::mpl::eval_if lub coś podobnego, aby to rozwiązanie działało.

Alternatywnie, możesz mieć specjalizację częściowego szablonu części głównej, która zatrzymuje rekurencję, jeśli warunek zostanie spełniony, tak jak w odpowiedzi K-ballos.

Właściwie wolałbym kod, który stosuje leniwą ocenę niż częściową specjalizację, ponieważ wydaje mi się, że łatwiej jest ją zrozumieć, a hałas przychodzący z szablonami jest niższy.

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.

ja nie widzę wariant podstawowy specjalizacji dla isqrt_impl. Aby złamać tę rekursję, musisz mieć specjalizację szablonu dla przypadku podstawowego. Oto prosta próba:

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