Вычислить n-е простое число во время компиляции

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

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

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

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

Я сомневаюсь, что ваша 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.

У вас, кажется, гораздо более здоровенное оборудование, чем у меня, и, конечно, больше памяти я
есть рутинный Lenovo ThinkPad T420, 4-х ядерный i5, 8 Гб оперативной памяти, 8 Гб подкачки, работающий под 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 не честно и прямо в 23 раза быстрее, чем YourNthPrime.
сломанные тайминги предполагают, что MyNthPrime на самом деле вокруг
В 2,75 раза быстрее, чем YourNthPrime на время пользователя. Но они также показывают
тот YourNthPrimeСтрой действительно потерял ферму в реальном времени. Что это было
делать для бесплодных 9/10-х его существования? Обмен, конечно.

Обе сборки высмеивали 95% моей 8 ГБ оперативной памяти в течение 45 секунд, но MyNthPrime
возглавил там и не поменялся. YourNthPrime продолжал есть своп
до 3,9 ГБ, и задолго до этого все мои процессоры дремали.

Этот момент примечателен, если принять его с тем фактом, что 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 на пути вниз ограничен
в конец списка с этой точки.

Вы предполагаете, что метапрограмма Sieve of Erathosthenes может
скомпилируйте быстрее, и вы правы. В качестве основного генератора, сито лучше
теоретическая сложность, чем судебное деление. Элегантный шаблон
реализация метапрограммы Питер Симонс, является
Вот, начиная с 2006 года или раньше. (А также
как прокомментировал Питер Вуд, нескончаемое сито эратфосена
В метапрограмме появилась новость о том, что система шаблонов C ++ полна по Тьюрингу.)
С помощью средств C ++ 11 метапрограмма Саймонса может быть значительно сокращена, но
Я не думаю, что сделал намного более эффективным. Просто стоит, Симонс
Сита может генерировать во время компиляции все простые числа до 512 в
до 9 секунд на моем ThinkPad. Нужно -ftemplate-depth=4000 или же
около того, чтобы сделать это, но только около 0,5 ГБ памяти — еще больше
арест контрпример к народной мудрости, что большая глубина шаблона ==
большое использование памяти.

Таким образом, Сито Эратхофена покидает Судебную Дивизию, барахтаясь в пыли.
К сожалению, для вашей цели сито бесполезно. Это называется
сито потому что мы должны ввести верхний предел целого числа U и это
сит из составных чисел от 2 до U, оставляя простые числа.
Таким образом, чтобы применить его для нахождения именно N-го простого числа = Pn и не
возможно любой другой, вы должны так или иначе вычислить Pn каким-то другим способом,
дать сите верхний предел Pn + 1 (или же Pn + 2, за Pn > 2), затем
выбросить все Pi, 2 <= Pi < Pn, что он вернется к тебе и сохранит
Просто Pn что вы уже вычислили. Это неоперация.

Несколько комментаторов подчеркивают, что тождество любого N-го простого числа
вы могли бы сгенерировать метапрограммирование во время компиляции будет
известен заранее или рассчитывается заранее гораздо проще и значительно
быстрее значит. Я не могу не согласиться, но я поддерживаю ваше общее мнение, что
с возможностями C ++ 11 TMP делает огромный шаг вперед в направлении практической полезности
это стоит изучить — тем более, что все занимает минуту
компиляция прямо сейчас займет секунду в течение десятилетия.

Между тем, даже не выходя из наших невероятно сложных компиляторов C ++,
с такими проблемами TMP мы все еще можем испытать природу программирования
ранний компьютер, с тактовой частотой и памятью в K, на «языке», смоделированном плотно — но в рамках тайных ограничений! — на классической рекурсии
теория функций. Вот почему вы действительно должны любить их!

Я сам попробовал и написал следующую реализацию:

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 способом.

ответ Майка Кингхана заставил меня задуматься, чего я раньше не делал. Если создание экземпляра шаблона является такой проблемой, которая вызывает такое серьезное потребление памяти, как мы можем уменьшить это? В конце концов я придумал схему, в которой вместо пакета аргументов для всех найденных на данный момент простых чисел я использую цепочку типов, каждый из которых ссылается на предыдущий, и цепочку статических функций в этих типах, которые могут использовать функции из типов. до.

Результат, который я вставлю ниже, все еще намного медленнее, чем тот, который предложил 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