Replacement for ternary operator in template metaprogramming

Question

I am implementing a binomial coefficient (n choose k) function in C++. Besides using a "normal" function (which is evaluated at runtime) this also can be accomplished using template metaprogramming (when the arguments are known at compile time):

template <unsigned int n, unsigned int k>
struct Binomialkoeffizient {
    static const unsigned int value = Binomialkoeffizient<n, k-1>::value * (n-k+1) / k;
};

template <unsigned int n>
struct Binomialkoeffizient<n, 0> {
    static const unsigned int value = 1;
};

The drawback of this implementation is, that it does not make use of the theorem n choose k = n choose n-k in the cases where k > n/2. So unnecessary arithmetic overflow may occur, e.g. 49 choose 43 does overflow, whereas 49 choose 6 does not.

I have tried the following to improve this:

template <unsigned int n, unsigned int k>
struct Binomialkoeffizient {
    static const unsigned int value = (2*k > n) ? Binomialkoeffizient<n, n-k>::value : Binomialkoeffizient<n, k-1>::value * (n-k+1) / k;
};

template <unsigned int n>
struct Binomialkoeffizient<n, 0> {
    static const unsigned int value = 1;
};

Unfortunately, I get fatal error: template instantiation depth exceeds maximum of 900.

This seems to be caused by the fact, that the ternary operator is not evaluated during the process of recursive template instantiation.

What are possible alternatives to using ?: ?

I am interested in pre-C++11 solutions and newer solutions alike (maybe std::enable_if helps, but I do not know well about it).

Kinshasa

Have you tried using std::conditional? – Electromagnetism

Could you please elaborate more on this? I am not sure how to use it exactly. It also seems to only work with C++11 upwards. – Kinshasa

@Kinshasa Yes, it is C++11. Step 1: solve it in C++11 using std::conditional. Step 2: Write my::conditional in C++03. Step 3: Profit. – Ranged

@Yakk Now I finally know what ???? is. – Asparagine

Answer 1

After a night of sleep, I think I got the point with the std::conditional.

Edit: As @Yakk has proposed, I also have implemented the conditional myself.

This implementation works with all C++ standards:

#if __cplusplus >= 201103L
    // in C++11 and above we can use std::conditional which is defined in <type_traits>
    #include <type_traits>
    namespace my {
        using std::conditional;
    }
#else
    // in older C++ we have to use our own implementation of conditional
    namespace my {
        template <bool b, typename T, typename F>
        struct conditional {
            typedef T type;
        };

        template <typename T, typename F>
        struct conditional<false, T, F> {
            typedef F type;
        };
    }
#endif

template <unsigned int n, unsigned int k>
struct Binomialkoeffizient {
    static const unsigned int value = my::conditional< (2*k > n), Binomialkoeffizient<n, n-k>, Binomialkoeffizient<n, k> >::type::_value;
    static const unsigned int _value = Binomialkoeffizient<n, k-1>::_value * (n-k+1) / k;
};

template <unsigned int n>
struct Binomialkoeffizient<n, 0> {
    static const unsigned int value = 1;
    static const unsigned int _value = 1;
};

Suggestions on how to make the code more concise or elegant (is it really necessary to use the second static member _value ?) are warmly welcome.

Kinshasa

Answer 2

C++11 introduced the constexpr specifier,

...(which) declares that it is possible to evaluate the value of the function or variable at compile time. Such variables and functions can then be used where only compile time constant expressions are allowed (provided that appropriate function arguments are given). A constexpr specifier used in an object declaration implies const.

(quoted from http://en.cppreference.com/w/cpp/language/constexpr)

In practice, you can implement a function like this:

template<class T>
constexpr T binomial_coefficient(const T n, const T k)
{
    if ( 2 * k > n )
    {
        return binomial_coefficient(n, n - k);
    }
    else
    {
        return k ? binomial_coefficient(n, k - 1) * (n - k + 1) / k : 1;
    }
}

That can be evaluated at compile time. As an example, look at https://godbolt.org/g/b1MgFd where this snippet is compiled by different compilers and the line

constexpr auto value = binomial_coefficient(49, 43);

Become

mov     eax, 13983816

Backstairs

I think that multiple statements in a constexpr function is officially added in C++14. – Kerstin

@Kerstin You are right. In this particular case it is easily solved by using a single return with another conditional operator instead of the if I used. – Backstairs

Thanks for this suggestion. I have verified it by disassembling the object code with objdump and indeed the computed value was in the file. Interestingly, immediately using the value without prior assignment to a variable, e.g. std::cout << binomial_coefficient(49, 43); causes the value to NOT be computed at compile time. – Kinshasa

@Kinshasa Yes, please note also that if you declare that variable as const, clang doesn't compute it at compile time, while gcc does. – Backstairs

Answer 3

The answer with constexpr is the best way to do it assuming you are using a modern C++ compiler.

However, the following code is essentially an improvement of your code that avoid instantiating too much template. In effect, as far as I know when using template as in your example, the compiler will generate all template that are in a ternary expression and not only the one is the selected side.

template <unsigned int n, unsigned int k>
struct Binomialkoeffizient 
{
    static const unsigned int k2 = (2 * k > n) ? n - k : k;
    static const unsigned int value = Binomialkoeffizient<n, k2 - 1>::value * (n - k2 + 1) / k2 ;
};

template <unsigned int n>
struct Binomialkoeffizient<n, 0> {
    static const unsigned int value = 1;
};

By defining k2 I can remove one extra level when 2 * k > n is true.

If you are using a C++ 11 compiler, you could replace const by constexpr. Otherwise, using an unnamed enum might be preferable as otherwise, it is possible that the compiler still reserve memory for value member for each instantiation level.

Kerstin

Thanks for the good idea with the k2. Just in the case n=k, e.g. Binomialkoeffizient<49, 49>::value your program does not work, as it perpetuously instantiates new templates until reaching the limit. Adding a further spezialization template <unsigned int n> struct Binomialkoeffizient<n, n> { static const unsigned int value = 1; };helps. – Kinshasa

Answer 4

Let me share my attempt at binomial coefficients in compile time.

#include <iostream>

template<unsigned N, unsigned K, typename = unsigned> // last arg for sfinae
struct choose; // predeclaring template for use in choose_recursive

template<unsigned N, unsigned K>
struct choose_recursive // typical recursion for choose is done here
{
    constexpr static unsigned value = choose<N - 1, K - 1>::value + choose<N - 1, K>::value;
};

struct choose_invalid
{
    constexpr static unsigned value = 0;
};

template<unsigned N, unsigned K, typename>
struct choose {
    constexpr static unsigned value = std::conditional_t<
        N >= K, choose_recursive<N, K>, choose_invalid
        >::value;
};

template<unsigned N>
struct choose<N, 0> {
    constexpr static unsigned value = 1;
};

// sfinae to prevent this and previous specialization overlapping for (0, 0)
template<unsigned K>
struct choose <K, K, std::enable_if_t< 0 <  K, unsigned>> {
    constexpr static unsigned value = 1;
};

int main()
{
    std::cout << choose<5, 2>::value << std::endl;
    std::cout << choose<5, 3>::value << std::endl;
    std::cout << choose<20, 10>::value << std::endl;
    std::cout << choose<0, 0>::value << std::endl;
    std::cout << choose<0, 1>::value << std::endl;
    std::cout << choose<49, 43>::value << std::endl;
}

This solution will work properly for each choose function value fitting in unsigned type, thus actually fixing the overflowing issues OP has been facing. A bit of sfinae is used to allow only single specialization for choose<0, 0> to match, and std::conditional_t is used to account for cases where N < K.

Disembowel