decarbonizedzed

So I am working my way through the beta of Jamis Buck's incredible "The Ray Tracer Challenge:"

https://pragprog.com/book/jbtracer/the-ray-tracer-challenge

(He's the guy who wrote the best book I've ever read on maze algorithms. His writing style is casual, funny, and a pleasure to read, unlike many other computer science books which are as dry as a stale cracked and agonizing.)

Anyways, it's been a great opportunity for me. I've been working in C++, since I want to improve my C++11, C++14, and C++17 (since the last time I used C++ was probably in 2007, so I had a lot to learn). I'm trying to make implementations of matrix and vector as general as possible, and as much as I can, constexpr everything, which is proving to be difficult. It can be quite surprising what the compiler allows as constexpr and what it doesn't. (The idea of constexpr is that computation happens at compile time rather than run time. This substantially reduces your run time at the cost of somewhat increasing how long compilation takes.)

C++11 brought some interesting concepts to the table and was a huge leap forward from C++98, but that puts me in a position where I really have to catch up and burrow through C++11, C++14, and C++17. The language improvements are fantastic, but in some cases (e.g. constexpr koff), very challenging.

Here's some C++ code for calculating the Nth Fibonacci number:

1:  #include <iostream>  
2:    
3:  template<>  
4:  struct fibstruct<1> {  
5:    constexpr static size_t value() {  
6:      return 1;  
7:    }  
8:  };  
9:    
10:  template<>  
11:  struct fibstruct<0> {  
12:    constexpr static size_t value() {  
13:      return 1;  
14:    }  
15:  };  
16:    
17:  int main() {  
18:    std::cout << "Fib(100) = " << fibstruct<100>::value() << '\n';  
19:  }

Now, that works and the fib numbers are calculated at compile time, but it's hardly elegant. Fortunately, with relaxations being made to the constexpr keyword, in C++, this code reduces down to a single method that's much easier to parse:

1:  #include <iostream>  
2:    
3:  template<size_t N>  
4:  constexpr unsigned long fib() {  
5:    if constexpr(N < 2) return 1;  
6:    else return fib<N-1>() + fib<N-2>();  
7:  }  
8:    
9:  int main()  
10:  {  
11:    constexpr unsigned long fb = fib<100>();  
12:    std::cout << "Fib(100) = " << fb << '\n';  
13:  }

In conclusion, use the most recent version of C++ at your disposal, You'll thank me for it later.

Happy programming, all!

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-09-04

Formatting code for blogger

Fibonacci sequence, raytracing, templates, and constexpr... oh my!

2018-08-03

Fun with templates and constexpr