在编译时计算nth prime [英] Compute nth prime at compile time

问题描述

在我看来， constexpr 和模板参数包的C ++ 11功能强大到足以执行一些相当复杂的计算。我有一个实际应用的一个可能的例子是在编译时计算第n个素数。

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.

为了让我们了解我的绩效期望：我希望一些代码可以在合理的桌面硬件上在不到一秒的编译时间内找到第512个素数（即3671）。

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.

推荐答案

我实现了最简单的方法，不使用模板，它的工作原理：

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");

它需要增加constexpr-深度，但它很容易适应：

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

将 getPrimeLoop 的深度递减到对数，因此g ++可以使用默认深度（不包含可衡量的时间惩罚）完成：

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));
}

这篇关于在编译时计算nth prime的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！