Infinite recursion in Meta Integer Square

Question

Good afternoon,

My friend asks about converting the integer square root function to metafunction. 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 that for some reason he cannot use the new function:

 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 convert this into a template structure that calls it 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 causes infinite recursion (on GCC 4.6.1), and I cannot 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 everyone

Answer 1

Evaluating the default template is not lazy.

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

will always create an instance of the template, no matter what the condition. You need boost::mpl::eval_if or something similar to make this solution work.

Alternatively, you can have a specialized specialization with a base case that stops recursion if the condition is met, as in the K-ballos answer.

I would prefer code that uses some form of lazy partial specialization assessment, because I feel it is easier to understand and keep the noise that comes with the templates below.

Answer 2

Unfortunately, this causes infinite recursion (on GCC 4.6.1), and I cannot figure out what is wrong with the code.

I do not see the base case specialization for isqrt_impl . To break this recursion, you need to have specialized specialization for the base case. Here is a simple attempt:

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