在C ++ 11的特性，与constexpr和模板参数包，应该在我看来，有足够的强度来执行一些相当复杂的计算。 一个可能的例子，对此我有一个实际的应用是在编译时的第n个素数的计算。
我所要求的方式来实现这种计算。 如果不止一个解决方案提出，这可能对它们进行比较是很有意思。
为了让你的我的业绩预期的想法：我希望在不到一秒的编译时间上合理的桌面硬件一些代码，可以找到512个主要（这是3671）。
Answer 1:
我实现了最简单的方式，不使用模板在所有和它的工作原理：
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深入一点，但它在时间上轻松安装：
$ time g++ -c -std=c++11 vec.cpp -fconstexpr-depth=600
real 0m0.093s
user 0m0.080s
sys 0m0.008s
以下特技减少的深度getPrimeLoop递归对数，所以克++可以与默认深度（不可测量的时间损失）完成：
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));
}
Answer 2:
我怀疑您的1个第二个目标是内没有保安的任何硬件的范围。 不过我相信，下列元程序可以关闭就可以了很多：
#include <type_traits>
template<unsigned N>
using boolean = std::integral_constant<bool,N>;
template<unsigned N>
constexpr bool is_co_prime()
{
return true;
};
template<unsigned N, unsigned D>
constexpr bool is_co_prime()
{
return N % D != 0;
};
template<unsigned N, unsigned D0, unsigned D1, unsigned ...Di>
constexpr bool is_co_prime()
{
typedef typename std::conditional<
is_co_prime<N,D1>(),
typename std::conditional<
is_co_prime<N,Di...>(),
boolean<is_co_prime<N,D0>()>,
std::false_type
>::type,
std::false_type
>::type type;
return type::value;
};
template<unsigned N>
constexpr unsigned inc()
{
return N == 2 ? 3 : N + 2;
}
template<unsigned Counter, unsigned Candidate, unsigned ...Primes>
struct nth_prime;
template<unsigned Candidate, unsigned Prime, unsigned ...Primes>
struct nth_prime<0,Candidate,Prime,Primes...>
{
static const unsigned value = Prime;
};
template<unsigned Counter, unsigned Candidate = 2, unsigned ...Primes>
struct nth_prime
{
typedef typename std::conditional<
is_co_prime<Candidate,Primes...>(),
nth_prime<Counter - 1,inc<Candidate>(),Candidate,Primes...>,
nth_prime<Counter,inc<Candidate>(),Primes...>
>::type type;
static const unsigned value = type::value;
};
#include <iostream>
using namespace std;
int main()
{
cout << nth_prime<512>::value << endl;
return 0;
}
我称之为元程序MyNthPrime和打电话给你一个YourNthPrime。
你似乎比我的更为强大的硬件，当然更多的内存。 我有一个常规的联想ThinkPad T420，4核i5处理器，8GB内存，8GB的交换，运行Linux Mint的14，内核3.5.0。 你汇报你花3分钟。 建立你YourNthPrime。 通过将测量time命令，它需要我35分钟。 建立YourNthPrime，没有运行任何应用程序，但终端和系统监控。
编译器GCC是4.7.2和命令行选项有：
-Wall -O0 -std=c++11 -ftemplate-depth=1200
在经过时间的分解为：
real 34m2.534s
user 3m40.414s
sys 0m33.450s
我花了1.5分钟打造MyNthPrime，具有：
-Wall -O0 -std=c++11 -ftemplate-depth=2100
而经过时间分解为：
real 1m27.832s
user 1m22.205s
sys 0m2.612s
这-ftemplate-depth=2100是不是一个错字换位。 更多的这种联系。
MyNthPrime是不公平和正视比YourNthPrime快23倍。 破烂的时机表明，MyNthPrime实际上是围绕2.75倍的速度作为YourNthPrime用户时间。 但他们也表明YourNthPrime的构建真的失去实时农场。 究竟是什么做其存在的无果而终9 /十分之？ 交换，当然。
双方建立嘲笑我的8GB的系统内存的95％以内，45秒，但MyNthPrime平顶身边有和没有掉。 YourNthPrime继续吃交换空间达到峰值3.9GB，不久，我的所有CPU都打瞌睡。
当你把它用事实MyNthPrime需要获得关于两倍这一点是值得注意的-ftemplate-depth为YourNthPrime。 民间的智慧是一个奢侈的-ftemplate-depth是毁掉超常程序编译时间在路上，因为这等同于奢侈的内存消耗，其中只有滑入过度交换，你就看油漆干燥。 但YourNthPrime和MyNthPrime的决胜不承担这一点-恰恰相反。 我采取的教训就是要你必须实例递归模板深度并不总是模板实例化必须执行的数量的一个很好的措施，它是你的内存资源事项的数量。
虽然他们不看表面上相似，MyNthPrime和YourNthPrime，都实现了黄金一代的试除法算法。 MyNthPrime是更快只是因为它是相当精明的多编码并节约递归模板实例，而内存的他们狼吞虎咽起来。
YourNthPrime字段4个递归模板计算， 全部消耗相同的递归可变参数模板参数列表 。 MyNthPrime场2：它只是提供有关一半的巨大实例做编译器。
YourNthPrime（因为我读它）感知在手上的素数上升的顺序做了试部门的潜在效率-因为朝着更小的素数师成功增加机会; 而一旦在手的黄金超过候选数的1/2分割，机会是0先打最可能的除数和优化您一个快速的判决和出口的前景。 但要利用这种效率的障碍是，在手的素数是通过在其头部总是最大的一个可变参数模板参数列表所表示的事实。 为了克服这个障碍YourNthPrime展开递归可变参数模板函数lastArg<>()有效地逆转，其中在手素数中的分裂被消耗的顺序。
lastArg<>()呈现手素数的模板函数：
template<unsigned i, unsigned head, unsigned... tail>
constexpr bool isPrime() {
return i % head && isPrime<i, tail...>();
}
在为下一个候选的递归审判庭升序i的素数head, tail... 。 它在这里我想你看lastArg<>()来支付方式，确保head永远是让你指出的昂贵的右手边，他下一个最佳的前景&& 。
但要实现这一lastArg<>()本身递归遍历手素数的整个列表在每次调用之前，你甚至得到有关裁决的机会i 。 因此，它会更便宜只是为了让isPrime<>()遍历手头的素数，只要它需要，测试i为它去，免去lastArg<>()并保存其所有的递归实例。
通过完成工作isPrime<>()在YourNthPrime -递归试除法-在MyNthPrime完成由：
template<unsigned N, unsigned D0, unsigned D1, unsigned ...Di>
constexpr bool is_co_prime()
{
typedef typename std::conditional<
is_co_prime<N,D1>(),
typename std::conditional<
is_co_prime<N,Di...>(),
boolean<is_co_prime<N,D0>()>,
std::false_type
>::type,
std::false_type
>::type type;
return type::value;
};
is_co_prime<>()采用10条线做什么is_prime<>()则在一次，我可以在一个线路也做它：
return is_co_prime<N,D0>() && is_co_prime<N,D1,Di...>();
可能是函数体。 但丑痛击漂亮这里的效率。 每次is_prime<>()具有递归到尾部，即尾只有一个短素比以前。 每次is_co_prime<>()所要做的尾部是两个素数短于它以前同样的事情。 其尾部递归是在比那些在最坏情况下较浅is_prime<>()并且存在只能一半多。
is_co_prime<>()将所述候选号N由右手-最小，有可能的-任何一对第一可用除数的，并在成功时返回无素数; 否则递归到任何除数仍于左右一对，并继续下一个，但一直到成功或耗尽的审判庭。 任何已经尝试过的最有可能的除数 - 只有在用尽它由原始对的更大的诉诸审判庭。 并在每个中间较小的递归同样，最不容易被除数上次尝试。
尽管这种算法可以看出，迅速到达的小和更有可能除数N ，痒将持续至直获得到最小的其中第一和试戴在真降序可能性，因为每lastArg<>() 我们要平息这种痒与的“让直行到最小”，当它在列表的尾部，将是自身必须递归在整个列表中的元功能的方式之前，我们甚至开始认同与审判部门。 实施is_co_prime<>()会让我们在列表中向下做审判庭，因为它这样做“一次一个两步”。
诚然，有时它会不幸“步过”的最大除数N第一次，然后就不会再找到它之前，除非它见底和向后递归该名单。 但是，一旦N大足以令它无论是否存在将主要是至少一个较小的除数进一步在右边，这将是非常不幸的错过了所有的人。 所以跳过途中最大的风险是向下没什么大不了的。 也请记住，有没有打算在途中任何除数下来，直到我们到达N/2点。 通过跳过一些的一个和唯一的除数是指递归的最坏情况下的垃圾N在一路下跌仅限于从该点列表的尾部。
你猜测，Erathosthenes的筛元程序可能编译更快，你是对的。 作为主要发电机，筛具有比审判庭更好的理论的复杂性。 通过优雅的模板元编程实现彼得·西蒙斯 ，就是在这里 ，从2006年或之前约会。 （正如彼得·伍德评论说，非终止Erathosthenes元程序的筛爆料，在C ++模板系统是图灵完备的。）用C ++ 11级的设施Simons的元编程可以大大缩写，但我不牛逼认为做更有效率。 只是它的立场，西蒙斯筛可以在编译时的不到9秒生成所有的素数达512个。 我的ThinkPad。 它需要-ftemplate-depth=4000点左右做，但只有约0.5GB的内存-一个更加止反以民间智慧大模板深入==大内存使用情况。
所以Erathosthenes'筛离开审判庭挣扎中的灰尘。 可悲的是，你锻炼的目的，筛是没有用的。 这就是所谓的筛子 ，因为我们必须输入一个整数上限U并将筛2之间的合数出U ，留下的素数。 因此，为了应用它用于寻找准确的第N个素数= Pn ，而不是可能的任何其他，必须无论如何计算Pn以某种其他方式，得到筛的上限Pn + 1 （或Pn + 2 ，对于Pn > 2 ），则扔掉所有的Pi, 2 <= Pi < Pn ，它返回给你，只保留Pn ，你已经计算。 这是一个无操作。
一些评论者作出这样的身份第N任总理，你可能会因编译时元编程生成点将提前或事先可计算通过更简单，更快速大幅手段是已知的。 我完全同意，但我支持与C ++ 11级的设施，TMP需要对真实世界的效用巨大的步幅，非常值得探讨的普遍观点 - 更何况任何需要一分钟，以正确的编译现在就在十年内第二。
同时，甚至没有离开我们惊异复杂的C ++编译器，与TMP问题，这样我们仍然可以体验到在K的，编程早期的电脑，时钟速度和内存紧紧建模的“语言”的本质 - 但内神秘的限制！ - 经典的递归函数理论。 这就是为什么你真的要爱他们！
Answer 3:
我考虑了一试自己，写了下面的实现：
template<unsigned... args> constexpr unsigned countArgs();
template<> constexpr unsigned countArgs() { return 0; }
template<unsigned head, unsigned... tail>
constexpr unsigned countArgs() { return 1 + countArgs<tail...>(); }
template<unsigned last>
constexpr unsigned lastArg() { return last; }
template<unsigned head, unsigned next, unsigned... tail>
constexpr unsigned lastArg() { return lastArg<next, tail...>(); }
template<unsigned i> constexpr bool isPrime() { return true; }
template<unsigned i, unsigned head, unsigned... tail>
constexpr bool isPrime()
{ return i % head && isPrime<i, tail...>(); }
template<bool found, unsigned i, unsigned... primesSoFar> struct nextPrime
{ static constexpr unsigned val =
nextPrime<isPrime<i + 2, primesSoFar...>(), i + 2, primesSoFar...>::val; };
template<unsigned i, unsigned... primesSoFar> struct
nextPrime<true, i, primesSoFar...> { static constexpr unsigned val = i; };
template<unsigned n, unsigned... primesSoFar> struct nthPrimeImpl
{ static constexpr unsigned val = nthPrimeImpl<n - 1, primesSoFar...,
nextPrime<false, lastArg<primesSoFar...>(), primesSoFar...>::val>::val; };
template<unsigned... primesSoFar> struct nthPrimeImpl<0, primesSoFar...>
{ static constexpr unsigned val = lastArg<primesSoFar...>(); };
template<unsigned n>
constexpr unsigned nthPrime() {
return n == 1 ? 2 : nthPrimeImpl<n - 2, 3>::val;
}
constexpr unsigned p512 = nthPrime<512>();
static_assert(p512 == 3671, "computed incorrectly");
这需要增加的最大深度模板gcc超过900默认的（在我的GCC 4.7.2），例如，通过传递-ftemplate-depth=1200 。 它是太慢 ：它发生在我的硬件约3 分钟 。 所以对于不同的回答一些更高效的代码，我非常希望。
在计算方法上，上面确实有点像审判庭 。 一个埃拉托色尼筛可能会表现得更好，但到目前为止，我不能想办法写在一个constexpr兼容的方式。
Answer 4:
在由迈克金汉的回答让我沿着线我没有，虽然之前的想法。 如果模板实例化是导致如此严重的内存消耗这样的问题，我们如何能减少呢？ 我终于想出了一个方案，其中，而不是对所有的素数的参数包迄今发现的，我用的类型链，每一个之前引用的一个，和静态函数在这些类型的链条，可以使用来自类型的那些之前。
下面我将粘贴的结果仍然是慢了很多了一个由ZCH建议 ，但我觉得它足够有趣，分享，因为它可能是其他应用程序的有用的方法。
template<unsigned N> struct NthPrime {
typedef NthPrime<N - 1> previous;
static constexpr unsigned prime = previous::nextPrime();
static constexpr unsigned nextPrime() { return nextCoprime(prime + 2); }
static constexpr unsigned nextCoprime(unsigned x) {
// x is a candidate. We recurse to obtain a number which is
// coprime to all smaller primes, then check that value against
// the current prime.
return checkCoprime(previous::nextCoprime(x));
}
static constexpr unsigned checkCoprime(unsigned x) {
// if x is coprime to the current prime as well, then it is the
// next prime. Otherwise we have to try the next candidate.
return (x % prime) ? x : nextCoprime(x + 2);
}
};
template<> struct NthPrime<1> {
static constexpr unsigned prime = 2;
static constexpr unsigned nextPrime() {
return 3;
}
static constexpr unsigned nextCoprime(unsigned x) {
return x; // x is guaranteed to be odd, so no need to check anything.
}
};
template<unsigned n>
constexpr unsigned nthPrime() {
return NthPrime<n>::prime;
}
constexpr unsigned p512 = nthPrime<512>();
static_assert(p512 == 3671, "computed incorrectly");
上面的兽既需要到constexpr深度和模板深度修改。 下面的值是我的编译器尖锐边界。
time g++-4.7.2 -c -fconstexpr-depth=519 -ftemplate-depth=2042 -std=c++11 foo.cc
real 0m0.397s
user 0m0.368s
sys 0m0.025s
文章来源: Compute nth prime at compile time [closed]
