Compute nth prime at compile time

c++, c++11, compile-time, constexpr, template-meta-programming

Solution

I implemented the simplest possible way, not using templates at all and it works:

constexpr bool isPrimeLoop(int i, int k) {
    return (k*k > i)?true:(i%k == 0)?false:isPrimeLoop(i, k + 1);
}

constexpr bool isPrime(int i) {
    return isPrimeLoop(i, 2);
}

constexpr int nextPrime(int k) {
    return isPrime(k)?k:nextPrime(k + 1);
}

constexpr int getPrimeLoop(int i, int k) {
// i - nr of primes to advance
// k - some starting prime
    return (i == 0)?k:getPrimeLoop(i - 1, nextPrime(k + 1));
}

constexpr int getPrime(int i) {
    return getPrimeLoop(i, 2);
}

static_assert(getPrime(511) == 3671, "computed incorrectly");

It needs increased constexpr-depth a bit, but it fits in time easily:

$ time g++ -c -std=c++11 vec.cpp -fconstexpr-depth=600

real    0m0.093s
user    0m0.080s
sys 0m0.008s

The following trick reduces depth of `getPrimeLoop` recursion to logarithmic, so g++ can complete with default depth (without measurable time penalty):

constexpr int getPrimeLoop(int i, int k) {
    return (i == 0)?k:
        (i % 2)?getPrimeLoop(i-1, nextPrime(k + 1)):
        getPrimeLoop(i/2, getPrimeLoop(i/2, k));
}

Problem

The C++11 features, with `constexpr` and template argument packs, should in my opinion be strong enough to perform some rather complex computations. One possible example for which I have a practical application is the computation of the nth prime at compile time. I'm asking for ways to implement this computation. If more than one solution are proposed, it might be interesting to compare them. To give you an idea of my performance expectations: I'd hope for some code which can find the 512th prime (which is 3671) in less than one second compile time on reasonable desktop hardware.

Original source