Infinite Recursion in Meta Integer Square Root

c++, metaprogramming, recursion, square-root, templates

Solution

Template evaluation isn't lazy by default.

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

will always instantiate the template, no matter what the condition. You need `boost::mpl::eval_if` or something equivalent to get that solution to work.

Alternatively you can have a base case partial template specialization that stops the recursion if the condition is met, like in K-ballos answer.

I'd actually prefer code that uses some form of lazy evaluation over partial specialization because I feel it is easier to comprehend and keeps the noise that comes with templates lower.

Problem

Good day, A friend of mine is asking about transforming an integer square root function into a meta-function. Here is the original function: ``` unsigned isqrt(unsigned value) { unsigned sq = 1, dlt = 3; while(sq<=value) { sq += dlt; dlt += 2; } return (dlt>>1) - 1; } ``` I wrote a meta version using `constexpr`, but he said he can't use the new feature for some reason: ``` 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); } ``` So I thought it shouldn't be that hard to transform that into template struct that calls it self recursively: ``` 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; }; ``` Unfortunately, this is causing infinite recursion(on GCC 4.6.1) and I am unable to figure out what is wrong with the code. Here is the 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 ``` Thanks all,

Original source