Infinito recursividad en el Meta Square Root Entero

Question

Buenos días,

Un amigo mío está preguntando por la transformación de una función de raíz cuadrada entero en una función de meta. Esta es la función original:

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

me escribió una versión meta usando constexpr, pero dijo que no se puede utilizar la nueva característica por alguna razón:

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

así que pensé que no debería ser tan difícil de transformar esa estructura en la plantilla que llama a si mismo de forma recursiva:

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

Desafortunadamente, esto está causando la recursividad infinita (en GCC 4.6.1) y no soy capaz de averiguar lo que está mal w con el código. Aquí está el error:

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 

Gracias todos,

Answer 1

La evaluación de la plantilla no es floja por defecto.

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

siempre creará una instancia de la plantilla, sin importar la condición. Necesita boost::mpl::eval_if o algo equivalente para que esa solución funcione.

Como alternativa, puede tener una especialización de plantilla parcial de caso base que detiene la recursión si se cumple la condición, como en la respuesta de K-ballos.

Prefiero el código que utiliza alguna forma de evaluación perezosa sobre la especialización parcial porque me parece más fácil de comprender y mantiene el ruido que viene con las plantillas más bajas.

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.

no veo un caso base para la especialización isqrt_impl. Debe tener una especialización de plantilla para el caso base para interrumpir esta recursión. Aquí hay un intento simple en eso:

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