what is wrong with this template metaprogram to find square root?

user_12255534 0
Viewed 93

I was trying to code the O(N) solution to find the square root of a perfect square number using template metaprogramming in C++. Algorithm:

algorithm sqrt(N, start):
     if(start*start == N)
            return start
     else
            return sqrt(N, start+1)

i.e:

template<int value, int N>
struct sqrt
{
    enum { val = ((value*value == N) ? value : (sqrt<(value+1), N>::val)) };
};

and instantiating sqrt<1, 4> in main().

I'm running into "template instantiation depth exceeds maximum of 900" error, eventhough it has to stop try and instantiate when value is 2?

Am I missing something specific for template metaprogramming? Does it executes both side of the ternary operator, irrespective of the condition? Kindly help me figure this out?

template-meta-programming c++
1 Answers

sqrt<X,N> instantiates sqrt<X+1,N> and that instantiates sqrt<X+2,N> etc. it never stops.

Both branches are evaluated by the compiler, even if only one of them is taken. The compiler is not clever enough to see that the condition is false at some point and then sqrt<value+1,N> does not need to be instantiated. You have to tell it more explictly. (Actually more correct: The compiler does need to know both sides of the : to determine their common type, because thats what the conditional operators type is).

Since C++17 you can use constexpr if to get the false-branch discarded:

#include <iostream>


template<int value, int N>
int sqrt(){
    if constexpr (value*value == N) { 
        return value;
    } else {
        return sqrt<value+1,N>();
    }
    
};

int main()
{
    std::cout << sqrt<1,4>();
}

Before C++17 you could use template specialization as the stop condition for the recursion:

#include <iostream>


template<int value, int N>
struct sqrt
{
    enum { val = ((value*value == N) ? value : (sqrt<(value+1), N>::val)) };
};

template <int value>
struct sqrt<value,value*value> {
    enum { val = value };
};


int main()
{
    std::cout << sqrt<1,4>::val;
}

However, both will fail when N is not a square number. You should change the condition to value*value >= N to make sure the recursion always stops (and addtionally check if N == value*value).

Further I suggest to swap the order of the arguments so you can use a default 1 for value. Also the enum thingy looks a little outdated. I don't remember what restriction is was meant to overcome. Anyhow, you can simply use a static const val = ... instead.

user_41177280
Related