Какова наиболее эффективная функция проверки вершинной простейшей хвостовой части?
Я экспериментировал с метапрограммированием до этого момента:
// compiled on Ubuntu 13.04 with:
// clang++ -O3 -ftemplate-depth-8192 -fconstexpr-depth=4096 -std=c++11 -stdlib=libc++ -lcxxrt -ldl compile-time-primes.cpp -o compile-time-primes
// assembly output with:
// clang++ -S -mllvm --x86-asm-syntax=intel -O3 -ftemplate-depth-8192 -fconstexpr-depth=4096 -std=c++11 -stdlib=libc++ -lcxxrt -ldl compile-time-primes.cpp -o compile-time-primes.asm
#include <array>
#include <iostream>
template<typename T>
constexpr bool is_prime(T number, T limit, T counter)
{
return counter >= limit
? number % limit != 0
: number % counter
? is_prime(number, number / counter, counter + 2)
: false;
}
template<typename T>
constexpr bool is_prime(T n)
{
return n == 2 || n == 3 || n == 5
? true
: n <= 1 || n % 2 == 0
? false
: is_prime(n, n / 3, T{3});
}
template<size_t n>
struct print_below;
template<> struct print_below<2> { inline static void primes() { std::cout << 2; } };
template<size_t n>
struct print_below
{
inline static void primes()
{
print_below<n - 1>::primes();
constexpr bool is_n_prime = is_prime(n);
if(is_n_prime)
std::cout << ", " << n;
}
};
template <typename T, T... N>
struct primes { static const std::array<bool, sizeof...(N)> cache; };
template <typename T, typename L, T R>
struct append_param;
template <typename T, T... L, T R>
struct append_param<T, primes<T, L...>, R> { using primes = primes<T, L..., R>; };
template <size_t N>
struct indexer : append_param<size_t, typename indexer<N - 1>::primes, N - 1> {};
template <>
struct indexer<0> { using primes = primes<size_t>; };
template <typename T, T... N>
const std::array<bool, sizeof...(N)> primes<T, N...>::cache = {{ is_prime(N)... }};
int main()
{
std::cout << "Some primes: \n";
print_below<8000>::primes();
std::cout << std::endl;
const auto &primes_cache = indexer<1000>::primes::cache;
for(size_t i = 1; i < primes_cache.size(); ++i)
std::cout << i << (primes_cache[i] ? " is " : " is not ") << "prime" << std::endl;
}
Теперь мне интересно, есть ли лучший хвостовой рекурсивный алгоритм для is_prime что можно положить в constexpr функция.
Есть ли что-нибудь намного лучше, чем это?
- Требование: хвост должен быть рекурсивным.
- Желательно: чтобы поместиться в
constexprфункция.
Решение
Да.
Прежде всего, одним из ваших основных ограничений будет ваш предел глубины рекурсии. Ваш рекурс один раз для каждого нечетного числа из 3 в sqrt(N), С пределом рекурсии ~ 1000 это означает, что вы сможете обрабатывать только числа до 1 миллиона. Вам нужно уменьшить количество выполняемой вами рекурсии.
Чтобы сделать это, нужно выполнить поиск типа «разделяй и властвуй» для факторов вашего числа. N, Немного поработав, вы можете расширить это до предела порядка 2^1000 (т. е. другие вещи, кроме предела рекурсии, сначала не сработают).
Во-вторых, вместо проверки каждого нечетного числа, проверьте 6 мод 1 и 5, с особым случаем, чтобы проверить 2/3/5 в начале. Можно использовать более дальний паттерн, чем радиус 6.
В-третьих, существуют вероятностные тесты на простоту, которые достаточно надежны, и их использование является правильным ответом. Вы могли бы, вероятно, построить жестко закодированную таблицу чисел, для которых тест не пройден, проверить по этой таблице и выполнить тесты в противном случае, и сделать свой верхний предел намного, намного выше, чем вы можете сделать практически иначе.
Еще одна проблема, связанная с вашим дизайном, заключается в том, что он проверяет простые числа по одному: в идеале вы должны составить таблицу простых чисел и использовать их, чтобы помочь в простом тестировании. Некоторые компиляторы делают запоминание предыдущих результатов, вы можете посмотреть, как это использовать.
Другие решения
Других решений пока нет …