decarbonizedzed: August 2018

I guess I should never be surprised at inconsistencies in behaviour in C++ compilers.

I was playing around with templates and constexpr using clang++ / llvm 5.0, coding some basic combinatorial formulae, and I found a constexpr expression that seemed that it should be legitimate, but it refused to compile, complaining that the expression needed to be initialized by a constant expression.

Even setting -fconstexpr-steps and -fconstexpr-depth to ridiculously high values failed with the error:

constexpr evaluation hit maximum step limit; possible infinite loop?

Consulting on stackexchange, someone pointed out that it worked fine with g++, so I gave it a try with g++-7, at which point, some of my specializations of templates refused to compile with the error:

error: template argument '(N - 1)' involves template parameter(s)

In the end, this mess was the result:

/**
 * constexpr_01.cpp
 *
 * By Sebastian Raaphorst, 2018.
 */

#include <iostream>

// Silly clang defining GNUC.
#if defined(__GNUC__) && defined(__clang__)
#undef __GNUC__
#endif

using factorial_t = unsigned long long;

/***********************
 *** USING TEMPLATES ***
 ***********************/
template<size_t N>
struct factorial {
    // Make sure that we aren't overflowing.
    static_assert(N * factorial<N-1>::value > factorial<N-1>::value);
    enum: factorial_t { value = N * factorial<N-1>::value };
};

template<>
struct factorial<0> {
    enum: factorial_t { value = 1 };
};

template<>
struct factorial<1> {
    enum: factorial_t { value = 1 };
};

#ifdef __clang__
/**
 * This refuses to compile with g++:
 * error: template argument '(N - 1)' involves template parameter(s)
 */
template<size_t N, size_t R>
struct factorialRange {
    // Assert that we have valid parameters and aren't overflowing.
    static_assert(N >= R);
    static_assert(N * factorialRange<N-1, R>::value > factorialRange<N-1, R>::value);
    enum: factorial_t { value = N * factorialRange<N-1, R>::value };
};

template<size_t N>
struct factorialRange<N,N> {
    enum: factorial_t { value = 1 };
};

template<size_t N>
struct factorialRange<N,N-1> {
    enum: factorial_t { value = N };
};

template<size_t N, size_t R>
struct permutations {
    enum: factorial_t { value = factorialRange<N, N - R>::value };
};

template<size_t N, size_t R>
struct combinations {
    enum: factorial_t { value = permutations<N, R>::value / factorial<R>::value };
};
#endif


/**
 * Combinations based on the fact the nCr = (n-1)Cr + (n-1)C(r-1).
 * This allows us to calculate much higher values than using factorials, such as 50C30.
 */
template<size_t N, size_t R>
struct recursive_combinations {
    enum: factorial_t { value = recursive_combinations<N-1, R-1>::value
                              + recursive_combinations<N-1, R>::value};
};

template<size_t N>
struct recursive_combinations<N,0> {
    enum: factorial_t { value = 1 };
};

template<size_t N>
struct recursive_combinations<N,N> {
    enum: factorial_t { value = 1 };
};


/***********************
 *** USING CONSTEXPR ***
 ***********************/
constexpr const factorial_t ceFactorial(const size_t N) {
    if (N == 0 || N == 1) {
        return 1;
    } else return N * ceFactorial(N-1);
}

constexpr const factorial_t ceFactorialRange(const size_t M, const size_t N) {
    if (M == N) return M;
    else return M * ceFactorialRange(M-1, N);
}

constexpr const factorial_t cePermutations(const size_t N, const size_t R) {
    return ceFactorialRange(N, N-R);
}

constexpr const factorial_t ceCombinations(const size_t N, const size_t R) {
    return ceFactorialRange(N, R)/ceFactorial(N-R);
}

constexpr const factorial_t ceRecursiveCombinations(const size_t N, const size_t R) {
    if (R == N || R == 0) return 1;
    return ceRecursiveCombinations(N-1, R) + ceRecursiveCombinations(N-1, R-1);
}


int main() {
#ifdef __clang__
    std::cout << "*** CLANG ***" << std::endl;
#elif __GNUC__
    std::cout << "*** G++ ***" << std::endl;
#endif

    // Overflows should not compile. If we try to compile this with 23, the static assert fails.
    constexpr size_t max_value = 22;
    constexpr auto max_factorial = factorial<max_value>::value;
    std::cout << "Max factorial is " << max_value << "! = " << max_factorial << std::endl;

#ifdef __clang__
    constexpr auto combo1 = combinations<15, 8>::value;
    std::cout << "15C8 = " << combo1 << std::endl;
#endif

    //constexpr auto combo2 = ceCombinations(50, 30); // compiles, but overflows
    //constexpr auto combo3 = combinations<50, 30>::value; // refuses to compile due to static asserts

    // This on the other hand, is successful and generates the correct response, which can be held in memory.
    // It is simply the intermediate factorials that cannot be held in memory.
    constexpr auto combo2 = recursive_combinations<50, 30>::value;
    std::cout << "50C30 = " << combo2 << std::endl;

#ifdef __GNUC__
    /**
     * This refuses to compile with clang++:
     * constexpr evaluation hit maximum step limit; possible infinite loop?
     */
    constexpr factorial_t combo4 = ceRecursiveCombinations(50, 30);
    std::cout << "50C30 = " << combo4 << std::endl;
#endif
}

With g++:

*** G++ ***
Max factorial is 22! = 17196083355034583040
50C30 = 47129212243960
50C30 = 47129212243960

With clang++:

*** CLANG ***
Max factorial is 22! = 17196083355034583040
15C8 = 6435
50C30 = 47129212243960

In conclusion, C++ programming is an exercise in masochism.

decarbonizedzed

2018-08-03

Fun with templates and constexpr