Infinite Recursion in Meta Integer Square Root

Question

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,

What's actual recursion depth if you do that using a recursive function? — sharptooth, Oct 17 '11 at 15:29
@sharptooth It happens with any value, it is not that the used value is causing an overflow. — Khaled Alshaya, Oct 17 '11 at 16:07

score 7 · Answer 1 · answered Oct 17 '11 at 15:30

Unfortunately, this is causing infinite recursion (on GCC 4.6.1) and I am unable to figure out what is wrong with the code.

I don't see a base case specialization for isqrt_impl. You need to have a template specialization for the base case to break this recursion. Here is a simple attempt at that:

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

Thanks very much, I appreciate your answer. I didn't really understand why I need specialization in the first place. That's why I choose @pmr answer, but your answer is excellent. I will let my friend see your answer as a solution to his question. — Khaled Alshaya, Oct 17 '11 at 16:11
@AraK : This site allows you to reassign the selected answer. Just click on the empty "check mark" next to this answer. — Siu Ching Pong -Asuka Kenji-, Feb 09 '14 at 07:34

pmr · Accepted Answer · 2011-10-17T16:14:33.750

4

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.

edited Oct 17 '11 at 16:14

answered Oct 17 '11 at 15:30

pmr

58,701
10
113
156

Thanks, I didn't know the template would get instantiated no matter the condition in the ternary operator. It is crystal clear now. – Khaled Alshaya Oct 17 '11 at 16:09
1

@AraK I'll supplement my answer with K-ballos solution to have an accepted answer that is comprehensive. – pmr Oct 17 '11 at 16:10

Infinite Recursion in Meta Integer Square Root

2 Answers2

Linked