Какова самая эффективная функция проверки вершинного рекурсивно-первичного подтверждения?

Question

Я экспериментировал с мета-программирования на данный момент:

// 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.

Answer 1

Да.

Прежде всего, один из ваших основных пределов будет вашим пределом глубины рекурсии. Ваша сумма повторяется для каждого нечетного числа от 3 до sqrt(N). С пределом рекурсии ~ 1000 это означает, что вы сможете обрабатывать номера до 1 миллиона. Вам нужно уменьшить количество рекурсии, которую вы делаете.

Способ сделать это - сделать поиск и делиться факторами вашего номера N. С небольшим количеством работы вы можете увеличить это до предела порядка 2^1000 (т. Е. Другие вещи, кроме предела рекурсии, заставят его работать в первую очередь).

Во-вторых, вместо того, чтобы проверять каждое нечетное число, проверьте 6 мод 1 и 5, со специальным чехлом для проверки 2/3/5 в начале. Также могут использоваться более длинные ряды, а не только радиус 6.

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

Еще одна проблема с вашим дизайном заключается в том, что он проверяет простые числа за один раз: в идеале вы должны создать таблицу простых чисел и использовать их, чтобы помочь с вашим простым тестированием. Некоторые компиляторы сделают memoization предыдущих результатов, вы можете изучить его использование.